Hybrid scatter search and path relinking for the capacitated p-median problem

In this paper we propose heuristic algorithms for the capacitated p-median problem. In the first one solutions are obtained with Scatter Search whereas the second algorithm uses Path Relinking. A third approach that combines Path Relinking with Scatter Search is also analyzed. The GRASP methodology is used to generate the initial Reference Set both for Scatter Search and Path Relinking. Computational experiments have been carried out with different data sets in order to evaluate the performance of the approaches. In general, Scatter Search outperforms Path Relinking, but the use of Path Relinking prior to Scatter Search has shown to enhance the performance of Scatter Search, specially in terms of the computation times required, due to the improvement of the initial Reference Set. The obtained results, that have been compared with previous approaches, show the efficiency of the methods both in terms of the quality of the solutions found and of the required computation times, even for very large instances.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems

In this study, we improved the variable neighborhood search (VNS) algorithm for solving uncapacitated multilevel lot-sizing (MLLS) problems. The improvement is twofold. First, we developed an effective local search method known as the Ancestors Depth-first Traversal Search (ADTS), which can be embedded in the VNS to significantly improve the solution quality. Second, we proposed a common and efficient approach for the rapid calculation of the cost change for the VNS and other generate-and-test algorithms. The new VNS algorithm was tested against 176 benchmark problems of different scales (small, medium, and large). The experimental results show that the new VNS algorithm outperforms all of the existing algorithms in the literature for solving uncapacitated MLLS problems because it was able to find all optimal solutions (100%) for 96 small-sized problems and new best-known solutions for 5 of 40 medium-sized problems and for 30 of 40 large-sized problems.     

Primal-dual interior-point method for thermodynamic gas-particle partitioning

A mathematical model for the computation of the phase equilibrium and gas-particle partitioning in atmospheric organic aerosols is presented. The thermodynamic equilibrium is determined by the global minimum of the Gibbs free energy under equality and inequality constraints for a system that involves one gas phase and many liquid phases. A primal-dual interior-point algorithm is presented for the efficient solution of the phase equilibrium problem and the determination of the active constraints. The first order optimality conditions are solved with a Newton iteration. Sequential quadratic programming techniques are incorporated to decouple the different scales of the problem. Decomposition methods that control the inertia of the matrices arising in the resolution of the Newton system are proposed. A least-squares initialization of the algorithm is proposed to favor the convergence to a global minimum of the Gibbs free energy. Numerical results show the efficiency of the approach for the prediction of gas-liquid-liquid equilibrium for atmospheric organic aerosol particles.     

Analysis of the Structured Total Least Squares Problem for Hankel/Toeplitz Matrices

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) approach when structured matrices are involved and a similarly structured rank deficient approximation of that matrix is desired. In many of those cases the STLS approach yields a Maximum Likelihood (ML) estimate as opposed to, e.g., TLS.In this paper we analyze the STLS problem for Hankel matrices (the theory can be extended in a straightforward way to Toeplitz matrices, block Hankel and block Toeplitz matrices). Using a particular parametrisation of rank-deficient Hankel matrices, we show that this STLS problem suffers from multiple local minima, the properties of which depend on the parameters of the new parametrisation. The latter observation makes initial estimates an important issue in STLS problems and a new initialization method is proposed. The new initialization method is applied to a speech compression example and the results confirm the improved performance compared to other previously proposed initialization methods.     

An adaptive multiphase approach for large unconditional and conditional p-median problems

A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a “Local Search with Shaking” procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.     

Performance of the MOSA Method for the Bicriteria Assignment Problem

The classical linear Assignment problem is considered with two objectives. The aim is to generate the set of efficient solutions. An exact method is first developed based on the two-phase approach. In the second phase a new upper bound is proposed so that larger instances can be solved exactly. The so-called MOSA (Multi-Objective Simulated Annealing) is then recalled; its efficiency is improved by initialization with a greedy approach. Its results are compared to those obtained with the exact method. Extensive numerical experiments have been realized to measure the performance of the MOSA method.     

Subgradient Methods for Sharp Weakly Convex Functions

Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A variety of statistical and signal processing tasks come equipped with good initialization and provably lead to formulations that are both weakly convex and sharp. Therefore, in such settings, subgradient methods can serve as inexpensive local search procedures. We illustrate the proposed techniques on phase retrieval and covariance estimation problems.     

The accessibility arc upgrading problem

The accessibility arc upgrading problem (AAUP) is a network upgrading problem that arises in real-life decision processes such as rural network planning. In this paper, we propose a linear integer programming formulation and two solution approaches for this problem. The first approach is based on the knapsack problem and uses the knowledge gathered from an analytical study of some special cases of the AAUP. The second approach is a variable neighbourhood search with strategic oscillation. The excellent performance of both approaches is demonstrated using a large set of randomly generated instances. Finally, we stress the importance of a proper allocation of scarce resources in accessibility improvement.     

Candidate groups search for K-harmonic means data clustering

Clustering is a very popular data analysis and data mining technique. K-means is one of the most popular methods for clustering. Although K-mean is easy to implement and works fast in most situations, it suffers from two major drawbacks, sensitivity to initialization and convergence to local optimum. K-harmonic means clustering has been proposed to overcome the first drawback, sensitivity to initialization. In this paper we propose a new algorithm, candidate groups search (CGS), combining with K-harmonic mean to solve clustering problem. Computational results showed CGS does get better performance with less computational time in clustering, especially for large datasets or the number of centers is big.     

Single-commodity robust network design problem: Complexity,instances and heuristic solutions

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {−1, 0, 1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.     

Embedding a novel objective function in a two-phased local search for robust vertex coloring

In this paper, we propose a two-phased local search for vertex coloring. The algorithm alternately executes two closely interacting functionalities, i.e., a stochastic and a deterministic local search. The stochastic phase is basically based on biased random sampling that, according to a probability matrix storing the probability a vertex can be assigned to a color, iteratively constructs feasible colorings. The deterministic phase, instead, consists in assigning sequentially, according to a given ordering, each vertex to the color which causes the lowest increase of the solution penalty, and then, when the schedule is constructed, swap operations are executed to improve the performance. The interaction between the two phases is implemented by tunnelling information of what happened during a phase to the successive ones. Beyond the algorithm scheme, the novelty of the approach stems from the fact that the objective function is not minimizing the number of colors but a new penalty function. The proposed approach is tested on known benchmarks for the studied problem available on the public domain. From a comparison to the state of the art it appears that the proposed approach is robust and is able to achieve best known results.     

A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem

The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.      

A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach

Genetic Algorithm (GA) is a popular heuristic method for dealing complex problems with very large search space. Among various phases of GA, the initial phase of population seeding plays an important role in deciding the span of GA to achieve the best fit w.r.t. the time. In other words, the quality of individual solutions generated in the initial population phase plays a critical role in determining the quality of final optimal solution. The traditional GA with random population seeding technique is quite simple and of course efficient to some extent; however, the population may contain poor quality individuals which take long time to converge with optimal solution. On the other hand, the hybrid population seeding techniques which have the benefit of good quality individuals and fast convergence lacks in terms of randomness, individual diversity and ability to converge with global optimal solution. This motivates to design a population seeding technique with multifaceted features of randomness, individual diversity and good quality. In this paper, an efficient Ordered Distance Vector (ODV) based population seeding technique has been proposed for permutation-coded GA using an elitist service transfer approach. One of the famous combinatorial hard problems of Traveling Salesman Problem (TSP) is being chosen as the testbed and the experiments are performed on different sized benchmark TSP instances obtained from standard TSPLIB [54]. The experimental results advocate that the proposed technique outperforms the existing popular initialization methods in terms of convergence rate, error rate and convergence time.     

Adaptive and restarting techniques-based algorithms for circular packing problems

In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle’s “best” position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.     

Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing

An approach is presented for treating discrete optimization problems mapped on the architecture of the Hopfield neural network. The method constitutes a modification to the local minima escape (LME) algorithm which has been recently proposed as a method that uses perturbations in the network's parameter space in order to escape from local minimum states of the Hopfield network. Our approach (LMESA) adopts this perturbation mechanism but, in addition, introduces randomness in the selection of the next local minimum state to be visited in a manner analogous with the case of Simulated Annealing (SA). Experimental results using instances of the Weighted Maximum Independent Set (MIS) problem indicate that the proposed method leads to significant improvement over the conventional LME approach in terms of quality of the obtained solutions, while requirinŗ & g a comparable amount of computational effort.     

Phase Retrieval with One or Two Diffraction Patterns by Alternating Projections with the Null Initialization

Alternating projection (AP) of various forms, including the parallel AP (PAP), real-constrained AP (RAP) and the serial AP (SAP), are proposed to solve phase retrieval with at most two coded diffraction patterns. The proofs of geometric convergence are given with sharp bounds on the rates of convergence in terms of a spectral gap condition. To compensate for the local nature of convergence, the null initialization is proposed to produce good-quality initial guess. Numerical experiments show that the null initialization is more accurate than the spectral initialization and that AP converges faster to the true object than other iterative schemes such as the Wirtinger flow (WF). In numerical experiments AP with the null initialization converges globally to the true object.     

A Tabu Search with Slope Scaling for the Multicommodity Capacitated Location Problem with Balancing Requirements

In this paper, a tabu search heuristic is combined with slope scaling to solve a discrete depot location problem, known as the multicommodity location problem with balancing requirements. Although the uncapacitated version of this problem has already been addressed in the literature, this is not the case for the more challenging capacitated version, where each depot has a fixed and finite capacity. The slope scaling approach is used during the initialization phase to provide the tabu search with good starting solutions. Numerical results are reported on various types of large-scale randomly generated instances. The quality of the heuristic is assessed by comparing the solutions obtained with those of a commercial mixed-integer programming code.     

DBR理论求解柔性作业车间调度问题

针对柔性作业车间调度完工时间最小问题,提出一种结合DBR(鼓-缓冲器-绳子)理论和改进遗传算法的方法。在问题初始化时,建立瓶颈机器识别机制改善初始化方法,提高初始解的质量;在运算过程中依据关键路径建立瓶颈机器的识别机制和调度策略。为了更好保留每代中的优良解,采用外部精英库对优良解进行解保留。运用提出的算法求解基准测试问题,实验结果验证了算法的可行性和有效性。     

Swarm contours: A fast self‐organization approach for snake initialization

A major obstacle in real‐time performance of a visual tracking system is its initialization phase. Inspired by social behavior in fish and ant groups, a fast self‐organization approach to active‐contour initialization is proposed. Contours are emerged during two separate phases of aggregation and self‐assembly. Aggregation is achieved by a superposition of simpler behaviors, hunting, avoidance, and opportunism. Self‐assembly, which constitutes the explicit contour formation, occurs by mating behavior when the swarm becomes quite stable. Experiments indicate that the proposed method outperforms exhaustive image search for finding contours in high resolutions. © 2006 Wiley Periodicals, Inc. Complexity 12: 41–52, 2006