The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

Branch-and-cut algorithms for the split delivery vehicle routing problem

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.     

Exact solution of the soft-clustered vehicle-routing problem

The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We show that even with all the recent acceleration techniques (e.g., partial pricing, bidirectional labeling, decremental state space relaxation) available for SPPRC labeling algorithms, the solution of the subproblem remains extremely difficult. The main contribution is the modeling and solution of the subproblem using a branch-and-cut algorithm. The conducted computational experiments prove that branch-and-price equipped with this integer programming-based approach outperforms sophisticated labeling-based algorithms by one order of magnitude. The largest SoftCluVRP instances solved to optimality have more than 400 customers or more than 50 clusters.     

On the m-capacitated peripatetic salesman problem with capacity restrictions

We consider a special case of the problem of finding m Hamiltonian cycles with capacity restrictions on the number of usages of the edges (m-Capacitated Peripatetic Salesman Problem or m-CPSP): the minimization and maximization 2-CPSP with edge weights chosen from an integer segment {1, q} with the edges capacities given as independent identically distributed random variables equal to 2 with probability p and 1 with probability (1 ? p). Some polynomial algorithms are proposed for 2-CPSP_min and 2-CPSP_max with average performance guarantees. In particular, when the edge weights are equal to 1 and 2, the algorithms have approximation ratios (19 ? 5p)/12 and (25 + 7p)/36 for the minimization and the maximization problem correspondingly.     

The Attractive Traveling Salesman Problem

In the Attractive Traveling Salesman Problem the vertex set is partitioned into facility vertices and customer vertices. A maximum profit tour must be constructed on a subset of the facility vertices. Profit is computed through an attraction function: every visited facility vertex attracts a portion of the profit from the customer vertices based on the distance between the facility and customer vertices, and the attractiveness of the facility vertex. A gravity model is used for computing the profit attraction. The problem is formulated as an integer non-linear program. A linearization is proposed and strengthened through the introduction of valid inequalities, and a branch-and-cut algorithm is developed. A tabu search algorithm is also implemented. Computational results are reported.     

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.     

A Branch-and-Cut-and-Price Approach for the Capacitated m-Ring-Star Problem

The Capacitated m-ring-star Problem is a variant of the classical one-depot capacitated vehicle routing problem in which a customer is either on a route or is connected to another customer or to some Steiner point present in a route. We develop a new exact algorithm for this problem using a branch-and-cut-and-price approach and compare its performance with that of a branch-and-cut algorithm proposed earlier in the literature. Computational results show that the new algorithm outperforms the branch-and-cut one in many instance classes.     

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.     

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.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

A new branch-and-cut algorithm for the capacitated vehicle routing problem

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.     

The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time.     

Efficient elementary and restricted non-elementary route pricing

Column generation is involved in the current most efficient approaches to routing problems. Set partitioning formulations model routing problems by considering all possible routes and selecting a subset that visits all customers. These formulations often produce tight lower bounds and require column generation for their pricing step. The bounds in the resulting branch-and-price are tighter when elementary routes are considered, but this approach leads to a more difficult pricing problem. Balancing the pricing with route relaxations has become crucial for the efficiency of the branch-and-price for routing problems. Recently, the ng-routes relaxation was proposed as a compromise between elementary and non-elementary routes. The ng-routes are non-elementary routes with the restriction that when following a customer, the route is not allowed to visit another customer that was visited before if they belong to a dynamically computed set. The larger the size of these sets, the closer the ng-route is to an elementary route. This work presents an efficient pricing algorithm for ng-routes and extends this algorithm for elementary routes. Therefore, we address the Shortest Path Problem with Resource Constraint (SPPRC) and the Elementary Shortest Path Problem with Resource Constraint (ESPPRC). The proposed algorithm combines the Decremental State-Space Relaxation technique (DSSR) with completion bounds. We apply this algorithm for the Generalized Vehicle Routing Problem (GVRP) and for the Capacitated Vehicle Routing Problem (CVRP), demonstrating that it is able to price elementary routes for instances up to 200 customers, a result that doubles the size of the ESPPRC instances solved to date.     

IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation

We present a new method for solving stochastic programs with joint chance constraints with random technology matrices and discretely distributed random data. The problem can be reformulated as a large-scale mixed 0–1 integer program. We derive a new class of optimality cuts called IIS cuts and apply them to our problem. The cuts are based on irreducibly infeasible subsystems (IIS) of an LP defined by requiring that all scenarios be satisfied. We propose a method for improving the upper bound of the problem when no cut can be found. We derive and implement a branch-and-cut algorithm based on IIS cuts, and refer to this algorithm as the IIS branch-and-cut algorithm. We report on computational results with several test instances from optimal vaccine allocation. The computational results are promising as the IIS branch-and-cut algorithm gives better results than a state-of-the-art commercial solver on one class of problems.     

An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices

The multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route lies within a given distance of a route. This paper tackles a particular case of m-CTP where only the restriction on the number of vertices is considered, i.e., the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a metaheuristic. To develop the branch-and-cut algorithm, we use a new integer programming formulation based on a two-commodity flow model. The metaheuristic is based on the evolutionary local search (ELS) method proposed in [23]. Computational results are reported for a set of test problems derived from the TSPLIB.     

Designing WDM Optical Networks Using Branch-and-Price

In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design.     

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound profits much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch-and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.     

A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.