A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999     

Integer linear programming formulations of multiple salesman problems and its variations

In this paper, we extend the classical multiple traveling salesman problem (mTSP) by imposing a minimal number of nodes that a traveler must visit as a side condition. We consider single and multidepot cases and propose integer linear programming formulations for both, with new bounding and subtour elimination constraints. We show that several variations of the multiple salesman problem can be modeled in a similar manner. Computational analysis shows that the solution of the multidepot mTSP with the proposed formulation is significantly superior to previous approaches.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

A simple LP relaxation for the asymmetric traveling salesman problem

It is a long-standing open question in combinatorial optimization whether the integrality gap of the subtour linear program relaxation (subtour LP) for the asymmetric traveling salesman problem (ATSP) is a constant. The study on the structure of this linear program is important and extensive. In this paper, we give a new and simpler LP relaxation for the ATSP. Our linear program consists of a single type of constraints that combine both the subtour elimination and the degree constraints in the traditional subtour LP. As a result, we obtain a much simpler relaxation. In particular, it is shown that the extreme solutions of our program have at most 2n ? 2 non-zero variables, improving the bound 3n ? 2, proved by Vempala and Yannakakis, for the ones obtained by the subtour LP. Nevertheless, the integrality gap of the new linear program is larger than that of the traditional subtour LP by at most a constant factor.     

A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

A parallel branch and bound algorithm that solves the asymmetric traveling salesman problem to optimality is described. The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure. The algorithm is organized around a data flow framework for parallel branch and bound. The algorithm begins by converting the cost matrix to a sparser version in such a fashion as to retain the optimality of the final solution. Computational results are presented for three different classes of problem instances: (1) matrix elements drawn from a uniform distribution of integers for instances of size 250 to 10 000 cities, (2) instances of size 250 to 1000 cities that concentrate small elements in the upper left portion of the cost matrix, and (3) instances of size 300 to 3000 cities that are designed to confound neighborhood search heuristics.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well-known relaxations of the TSP are the subtour elimination problem and the 2-matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT ≤4/3, and that 2M/SUBT ≤10/9.In this paper, we exploit the structure of certain 1/2-integer solutions for the subtour elimination problem in order to obtain low cost TSP and 2-matching solutions. In particular, we show that for cost functions for which the optimal subtour elimination solution found falls into our classes, the above two conjectures are true. Our proofs are constructive and could be implemented in polynomial time, and thus, for such cost functions, provide a 4/3 (or better) approximation algorithm for the TSP.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

A comparison of lower bounds for the symmetric circulant traveling salesman problem

When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559-1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138-1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].     

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.     

Generating partitions of a graph into a fixed number of minimum weight cuts

In this paper, we present an algorithm for the generation of all partitions of a graph G with positive edge weights into k mincuts. The algorithm is an enumeration procedure based on the cactus representation of the mincuts of G. We report computational results demonstrating the efficiency of the algorithm in practice and describe in more detail a specific application for generating cuts in branch-and-cut algorithms for the traveling salesman problem.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.     

Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem

This paper presents a new model for a special type of traveling salesman problem called the High Multiplicity Asymmetric Traveling Salesman Problem (HMATSP). The formulation adopts a flow-based subtour elimination structure and establishes its validity for this problem. Also, we present computational results to demonstrate the efficacy of our modeling approach. The model is then incorporated as a substructure in a formulation for the lot-sizing problem involving parallel machines and sequence-dependent setup costs, also known as the Chesapeake Problem, and related test problems are solved to optimality for the first time in the literature.     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with different basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between cities. We then introduce an exact reformulation that generates a family of successively tighter lower bounds, all solvable in polynomial time. We show that the base member of this family yields a bound greater than or equal to the well-known Held-Karp bound, obtained by solving the linear programming relaxation of the TSP’s integer programming arc-based formulation.     

Euclidean semi-matchings of random samples

A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semi-matching. The main result is the determination of the asymptotic behavior of the length of the minimal semi-matching. It is analogous to the theorem of Beardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of non-random Euclidean semi-matchings and large deviation inequalities for random semi-matchings are also given.Research supported in part by NSF Grant #DMS-8812868, ARO contract DAAL03-89-G-0092.P001, AFOSR-89-08301.A and NSA-MDA-904-89-2034.