Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem

In this paper we develop, study and test new neighborhood structures for the Hop-constrained Minimum Spanning Tree Problem (HMSTP). These neighborhoods are defined by restricted versions of a new dynamic programming formulation for the problem and provide a systematic way of searching neighborhood structures based on node-level exchanges. We have also developed several local search methods that are based on the new neighborhoods. Computational experiments for a set of benchmark instances with up to 80 nodes show that the more elaborate methods produce in a quite fast way, heuristic solutions that are, for all cases, within 2% of the optimum.     

Relaxations and discretizations for the pooling problem

The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives new insights on prevalent techniques. We also present new ideas for computing dual bounds on the global optimum by solving high-dimensional linear programs. Finally, we propose discretization methods for inner approximating the feasible region and obtaining good primal bounds. Valid inequalities are derived for the discretized models, which are formulated as mixed integer linear programs. The strength of our relaxations and usefulness of our discretizations is empirically validated on random test instances. We report best known primal bounds on some of the large-scale instances.     

Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and the other involving an exhaustive search of the insertion neighborhood. We also present techniques to significantly speed up the search of the two neighborhoods. Our computational experiments show that the speed up techniques are effective, and our tabu search implementations are competitive. Our tabu search implementations improved previously known best solutions for 23 out of the 43 large sized SRFLP benchmark instances.     

New relationships for multi-neighborhood search for the minimum linear arrangement problem

We develop a series of theorems about the graph structure of the classical Minimum Linear Arrangement (MinLA) problem which disclose properties that can be exploited by Multi-Neighborhood Search (MNS) algorithms. As a foundation, we differentiate between swaps of labels attached to adjacent and non-adjacent nodes to create two new neighborhood classes, and show how our theorems yield efficient algorithms for updating key arrays used by local search procedures. In addition, we introduce a class of neighborhoods called set-based neighborhoods supported by a theorem that identifies solutions (labelings) for the MinLA problem in polynomial time that dominate exponential numbers of alternative solutions. The component neighborhoods within this new neighborhood class can be applied in various sequences in conjunction with the first two new neighborhoods introduced. Our results also apply to problems with objectives different than those of MinLA. Finally, our results make it possible to exploit the new neighborhoods according to the user's choice of MNS protocols and alternative local search algorithms.     

A study on exponential-size neighborhoods for the bin packing problem with conflicts

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce \({\mathcal O}(1)\) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.     

A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

Decomposition methods for the lot-sizing and cutting-stock problems in paper industries

We investigate the one-dimensional cutting-stock problem integrated with the lot-sizing problem in the context of paper industries. The production process in paper mill industries consists of producing raw materials characterized by rolls of paper and cutting them into smaller rolls according to customer requirements. Typically, both problems are dealt with in sequence, but if the decisions concerning the cutting patterns and the production of rolls are made together, it can result in better resource management. We investigate Dantzig–Wolfe decompositions and develop column generation techniques to obtain upper and lower bounds for the integrated problem. First, we analyze the classical column generation method for the cutting-stock problem embedded in the integrated problem. Second, we propose the machine decomposition that is compared with the classical period decomposition for the lot-sizing problem. The machine decomposition model and the period decomposition model provide the same lower bound, which is recognized as being better than the linear relaxation of the classical lot-sizing model. To obtain feasible solutions, a rounding heuristic is applied after the column generation method. In addition, we propose a method that combines an adaptive large neighborhood search and column generation method, which is performed on the machine decomposition model. We carried out computational experiments on instances from the literature and on instances adapted from real-world data. The rounding heuristic applied to the first column generation method and the adaptive large neighborhood search combined with the column generation method are efficient and competitive.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

A new destructive bounding scheme for the bin packing problem

In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.     

Creating very large scale neighborhoods out of smaller ones by compounding moves

This paper discusses neighborhood search algorithms where the size of the neighborhood is “very large” with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way of creating and searching CIM neighborhoods for routing problems with side constraints. For such problems, the exact search of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows that CIM algorithms are very competitive approaches for solving vehicle routing problems. Overall, the solutions generated by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from the best-known solutions for large-scale capacitated VRP instances.     

A Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates

In this paper, we present a Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates. We introduce new lower bounds and we generalize some well-known dominance properties. Our procedure handles instances as large as 500 jobs although some 60 jobs instances remain open. Computational results show that the proposed approach outperforms the best known procedures.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

A general variable neighborhood search variants for the travelling salesman problem with draft limits

In this paper, we present two general variable neighborhood search (GVNS) based variants for solving the traveling salesman problem with draft limits (TSPDL), a recent extension of the traveling salesman problem. TSPDL arises in the context of maritime transportation. It consists of finding optimal Hamiltonian tour for a given ship which has to visit and deliver products to a set of ports while respecting the draft limit constraints. The proposed methods combine ideas in sequential variable neighborhood descent within GVNS. They are tested on a set of benchmarks from the literature as well as on a new one generated by us. Computational experiments show remarkable efficiency and effectiveness of our new approach. Moreover, new set of benchmarks instances is generated.     

Variable neighborhood search for the travelling deliveryman problem

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.     

A New Wide Neighborhood Primal–Dual Infeasible-Interior-Point Method for Symmetric Cone Programming

We present a new infeasible-interior-point method, based on a wide neighborhood, for symmetric cone programming. The convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the xs and sx directions. Moreover, we derive the complexity bound of the wide neighborhood infeasible interior-point methods that coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm.     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times

The Job Shop Scheduling Problem (JSP) is an example of a combinatorial optimization problem that has interested researchers for several decades. In this paper we confront an extension of this problem called JSP with Sequence Dependent Setup Times (SDST-JSP). The approach extends a genetic algorithm and a local search method that demonstrated to be efficient in solving the JSP. For local search, we have formalized neighborhood structures that generalize three well-know structures defined for the JSP. We have conducted an experimental study across conventional benchmark instances showing that the genetic algorithm exploited in combination with the local search, considering all three neighborhoods at the same time, provides the best results. Moreover, this approach outperforms the current state-of-the-art methods.