On the symmetric travelling salesman problem II: Lifting theorems and facets

Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.     

Maximum travelling salesman problem

We present different types of techniques for designing algorithms with worst-case performances for the Maximum Travelling Salesman Problem. Supported by Byelarussian Fundamental Science Found and DAAD     

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.      

Selective generalized travelling salesman problem

ABSTRACT

This paper introduces the Selective Generalized Traveling Salesman Problem (SGTSP). In SGTSP, the goal is to determine the maximum profitable tour within the given threshold of the tour’s duration, which consists of a subset of clusters and a subset of nodes in each cluster visited on the tour. This problem is a combination of cluster and node selection and determining the shortest path between the selected nodes. We propose eight mixed integer programming (MIP) formulations for SGTSP. All of the given MIP formulations are completely new, which is one of the major novelties of the study. The performance of the proposed formulations is evaluated on a set of test instances by conducting 4608 experimental runs. Overall, 4138 out of 4608 (~90%) test instances were solved optimally by using all formulations.     

An additive bounding procedure for the asymmetric travelling salesman problem

In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981). Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems.     

Bounds for the symmetric 2-peripatetic salesman problem

The 2-Peripatetic Salesman Problem (2-PSP) minimizes the total length of 2 edge-disjoint Hamil-tonian cycles. This type of problems arises in designing communication or computer networks, or whenever one aims to increase network reliability using disjoint tours. The NP-hardness of the 2-PSP is shown. Lower bound values are obtained by generalizing the 1-tree approach for the TSP to a 2 edge-disjoint 1-trees approach for the 2-PSP. One can construct 2 edge-disjoint 1-trees using a greedy algorithm, into which a partitioning procedure is incorporated that runs O(n ² log n) time. Upper bound solutions are obtained by two heuristics based on a lower bound solution and by a modified Savings heuristic for problems up to 140 cities.     

Universal conditions for algebraic travelling salesman problems to be efficiently solvable

We consider Travelling Salesman Problems (TSPs) where the cost of a tour is an algebraic composition of the cost coefficients that are elements of a totally ordered, commutative semigroup. Conditions for the cost matrix are stated which allow to solve these problems in polynomial time. In particular, we investigate conditions which guarantee that an optimal tour is pyramidal and can therefore be determined in O(n ²) time. Furthermore, we discuss TSP_s with Brownian as well as those with left-upper-triangular cost matrices.     

On estimating the distribution of optimal traveling salesman tour lengths using heuristics

The traveling salesman problem is an important combinatorial optimization problem due to its significance in academic research and its real world applications. The problem has been extensively studied and much is known about its polyhedral structure and algorithms for exact and heuristic solutions. While most work is concentrated on solving the deterministic version of the problem, there also has been some research on the stochastic TSP. Research on the stochastic TSP has concentrated on asymptotic properties and estimation of the TSP-constant. Not much is, however, known about the probability distribution of the optimal tour length. In this paper, we present some empirical results based on Monte Carlo simulations for the symmetric Euclidean and Rectilinear TSPs. We derive regression equations for predicting the first four moments of the distribution of estimated TSP tour lengths using heuristics. We then show that a Beta distribution gives excellent fits for small to moderate sized TSP problems. We derive regression equations for predicting the parameters of the Beta distribution. Finally we predict the TSP constant using two alternative approaches.     

A new class of cutting planes for the symmetric travelling salesman problem

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known comb inequalities, the path inequalities and the 3-star constraints as special cases. Its relation to the clique tree inequalities is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

Using cutting planes to solve the symmetric Travelling Salesman problem

Two algorithms using cutting planes are developed for solving the Travelling Salesman Problem. In both algorithms the problem is started with a subset of the set of constraints that define the problem (apart from integrality requirements).However, the two algorithms differ in the order in which the omitted constraints and the cutting planes that are required are generated.The computational experience obtained suggests that cutting planes can provide a competitive approach to other efficient methods of solving the problem.     

On the refinement of bounds of heuristic algorithms for the traveling salesman problem

A number of heuristics for the traveling salesman problem (TSP) rely on the assumption that the triangle inequality (TI) is satisfied. When TI does not hold, the paper proposes a transformation such that for the transformed problem the TI holds. Consequently, the bounds obtained for heuristics are valid with appropriate modification. Moreover, for a TSP satisfying TI the same transformation strengthens such bounds. The transformation essentially maps the problem into one that is minimal with respect to the property that TI holds. For the symmetric TSP the transformation is particularly simple. For an application of the transformation in the asymmetric case we need the dual solution of an assignment problem.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

Improving Christofides' lower bound for the traveling salesman problem

In 1972 Christofides introduced a lower bound for the Traveling Salesman Problem (TSP). The bound is based on solving repeatedly a Linear Assignment Problem. We relate the bound to the Complete Cycle Problem; as a consequence the correctness of the bound is easier to prove.

Further we give improvements for the bound in the symmetric case and we deal with the influence of the triangle equation together with the identification of non-optimal edges for the TSP. The improvements are illustrated by examples and computational results for large problems.     

A note on heuristics for the traveling salesman problem

We introduce subclasses of the traveling salesman problem (TSP) and analyze the behaviour of heuristics on them. We derive bounds for the performance of the algorithms.     

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

The travelling salesman problem (TSP)   is one of the most prominent NP-hard combinatorial optimisation problems. After over fifty years of intense study, the TSP continues to be of broad theoretical and practical interest. Using a novel approach to empirical scaling analysis, which in principle is applicable to solvers for many other problems, we demonstrate that some of the most widely studied types of TSP instances tend to be much easier than expected from previous theoretical and empirical results. In particular, we show that the empirical median run-time required for finding optimal solutions to so-called random uniform Euclidean (RUE) instances – one of the most widely studied classes of TSP instances – scales substantially better than Θ(2ⁿ)$\Theta (2^n)$ with the number n of cities to be visited. The Concorde solver, for which we achieved this result, is the best-performing exact TSP solver we are aware of, and has been applied to a broad range of real-world problems. Furthermore, we show that even when applied to a broad range of instances from the prominent TSPLIB benchmark collection for the TSP, Concorde exhibits run-times that are surprisingly consistent with our empirical model of Concorde’s scaling behaviour on RUE instances. This result suggests that the behaviour observed for the simple random structure underlying RUE is very similar to that obtained on the structured instances arising in various applications.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

On patching algorithms for random asymmetric travelling salesman problems

Let the arc-lengthsL _ij of a complete digraph onn vertices be independent uniform [0, 1] random variables. We consider the patching algorithm of Karp and Steele for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. We extend these ideas to thek-person travelling salesman problem and also consider the case where cities can be visited more than once.