A comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

Backbone guided tabu search for solving the UBQP problem

We propose a backbone-guided tabu search (BGTS) algorithm for the Unconstrained Binary Quadratic Programming (UBQP) problem that alternates between two phases: (1) a basic tabu search procedure to optimize the objective function as far as possible; (2) a strategy using the TS notion of strongly determined variables to alternately fix and free backbone components of the solutions which are estimated likely to share values in common with an optimal solution. Experimental results show that the proposed method is capable of finding the best-known solutions for 21 large random instances with 3000 to 7000 variables and boosts the performance of the basic TS in terms of both solution quality and computational efficiency.     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems

We study both weighted and unweighted unconstrained two-dimensional guillotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-search procedure introducing two strategies: Depth-first search and Hill-climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH /KD algorithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm uses also the KD algorithm for constructing new lower bounds and uses another one-dimensional knapsack for constructing refinement upper bounds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s algorithm (the unweighted case), and to Beasley's [2] approach (the weighted case) on some examples taken from the literature as well as randomly generated instances.     

The periodic vehicle routing problem with intermediate facilities

In this paper, we study an extension of the PVRP where the vehicles can renew their capacity at some intermediate facilities. Each vehicle returns to the depot only when its work shift is over. For this problem we propose a tabu search (TS) algorithm and present computational results on a set of randomly generated instances and on a set of PVRP instances taken from the literature.     

Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering

Minimum sum-of-squares clustering consists in partitioning a given set of n points into c clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. Recently, Sherali and Desai (JOGO, 2005) proposed a reformulation-linearization based branch-and-bound algorithm for this problem, claiming to solve instances with up to 1,000 points. In this paper, their algorithm is investigated in further detail, reproducing some of their computational experiments. However, our computational times turn out to be drastically larger. Indeed, for two data sets from the literature only instances with up to 20 points could be solved in less than 10 h of computer time. Possible reasons for this discrepancy are discussed. The effect of a symmetry breaking rule due to Plastria (EJOR, 2002) and of the introduction of valid inequalities of the convex hull of points in two dimensions which may belong to each cluster is also explored.     

An exact algorithm for the node weighted Steiner tree problem

The Node Weighted Steiner Tree Problem (NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances, derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem. Received: March 2005, Revised: September 2005 AMS classification: 68M10, 90C10, 90C57 This work has been partially supported by the Ministero dell'Istruzione, Universitá e Ricerca (MIUR), Italy     

A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.     

A 3-flip neighborhood local search for the set covering problem

The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n³), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances.     

An evolutionary heuristic for quadratic 0–1 programming

In this paper we present a heuristic algorithm for the well-known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.     

Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations

A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher-dimensional space by introducing variables Y _ij to represent each of the products x _i x _j of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using the (convex) SDP constraint Y - x x^T \succeq 0{Y - x x^T \succeq 0} and disjunctive programming. On the other hand, the main drawback of such an extended formulation is its huge size, even for problems for which the number of x _i variables is moderate. In this paper, we study methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology. We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore, we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint, we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a new eigen-reformulation for MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion paper even though our computing times are about 100 times smaller, on average. Second, on box-QP instances, the strengthened relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than 2 s, even for large instances with 100 variables; the SDP+RLT relaxations for the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver.     

The two-echelon production-routing problem

This paper introduces the Two-Echelon Production-Routing Problem. This problem is motivated from the petrochemical industry, enlarging the supply chain integration by taking into account production, inventory, and routing decisions in a two-echelon vendor-managed inventory system. We describe, model, and design a branch-and-cut (B&C) to solve the problem under different inventory policies. We also propose a novel exact algorithm, by employing parallel computing techniques, in order to combine local search procedures within a traditional B&C scheme. We evaluate the performance of our methods through extensive computational experiments, both by comparing the algorithms, the effectiveness of the different inventory policies, and the impact of these policies on the partial costs. We derive many managerial insights based on the results. We also validate our new exact algorithm by solving similar problems from the literature, such as the two-echelon multi-depot inventory-routing (2E-MDIRP) and the classical multi-vehicle production-routing problem (MV-PRP). Computational experiments show that our method is very competitive. Based on 512 experiments for the 2E-MDIRP, our algorithm was able to find 111 new best known solutions (BKS), besides proving 412 optimal solutions, against 298 from the literature. For 336 experiments over small and medium size MV-PRP instances, we proved 242 optimal solutions, 11 more than the exact methods from the literature, besides providing 95 new BKS. Moreover, we were the first to tackle large MV-PRP instances exactly, and in this case, our algorithm provides all BKS for instances up to 50 customers, 20 periods and 5 vehicles, outperforming all meta/matheuristics procedures from the literature.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.     

Tabu search for solving the black-and-white travelling salesman problem

The black-and-white travelling salesman problem (BWTSP) is an extension to the well-known TSP by partitioning the set of vertices into black and white vertices, and imposing cardinality and length constraints between two consecutive black vertices in a Hamiltonian tour. BWTSP has various applications in aircraft routing, telecommunication network design and logistics. In this paper, we develop several tabu search (TS) heuristics for solving the BWTSP. Our TS is built upon a new efficient neighbourhood structure, which exploits both the permutation and knapsack features of BWTSP. We also embed our TS as a heuristic procedure to improve the upper bound in a mixed-integer linear programming method. Extensive computational experiment on both benchmark and randomly generated instances shows effectiveness and efficiency of our algorithms. Our algorithms are able to obtain optimal and near optimal solutions to small instances in seconds, and find feasible solutions to large instances that have not been solved by the existing methods in the literature.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

Two exact algorithms for the capacitated p-median problem

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any ratio.Received: December 2002, Revised: August 2003AMS classification: 90C10, 90C27