Algorithms for the universal and a priori TSP

We present two simple results for generalizations of the traveling salesman problem (TSP): for the universal TSP, we show that one can compute a tour that is universally optimal whenever the input is a tree metric. A (randomized) O(logn)-approximation algorithm for the a priori TSP follows as a corollary.     

Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within at most a factor of 2. We consider the problem of finding among these tours the one that gives the closest approximation, i.e. the minimum-weight double-tree shortcutting. Previously, we gave an efficient algorithm for this problem, and carried out its experimental analysis. In this paper, we address the related question of the worst-case approximation ratio for the minimum-weight double-tree shortcutting method. In particular, we give lower bounds on the approximation ratio in some specific metric spaces: the ratio of 2 in the discrete shortest path metric, 1.622 in the planar Euclidean metric, and 1.666 in the planar Minkowski metric. The first of these lower bounds is tight; we conjecture that the other two bounds are also tight, and in particular that the minimum-weight double-tree method provides a 1.622-approximation for planar Euclidean TSP.     

Construction heuristics for the asymmetric TSP

Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.     

On the nearest neighbor rule for the traveling salesman problem

Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145-180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor above the length of the optimal tour.We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.     

The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms

We identify new solvable cases of the travelling salesman problem (TSP) by an indirect analysis that has useful consequences. First, we develop new procedures for the TSP that require only linear time to execute and yield TSP tours that are better than an exponential number of alternative tours. We then identify special subgraphs, easily generated, so that our method yields these outcomes for every instance of these subgraphs. Finally, when the associated costs satisfy prescribed conditions, we show the solutions produced by these algorithms are optimal and thus we have new solvable cases of the TSP. Besides possible practical applications to problems that may exhibit these cost conditions, our algorithms may also be applied as subroutines within more complex metaheuristics. Our methods extend in a natural way to bottleneck TSP formulations, and their underlying results raise new theoretical questions about the analysis of heuristics for hard combinatorial problems.     

The time dependent traveling salesman problem: polyhedra and algorithm

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.     

Multi-criteria TSP: Min and max combined

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3,3+ε)-approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we obtain an approximation performance of (1/2,log₂n+ε).     

General k-opt submoves for the Lin–Kernighan TSP heuristic

Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.     

Singly-implicit stabilized extended one-step methods for second-order initial-value problems with oscillating solutions

We introduce a new class of singly-implicit extended one-step methods for the numerical integration of second-order initial-value problems y″ = f(t, y), y(t₀) = η₀, y′(t₀) = η₁, with oscillating solutions. We first show that for third order, with two stages there exists a uniquely determined ‘almost’ P-stable method. We then investigate stability of the general class of fourth-order one-step methods. We first look for stabilized fourth-order methods with two stages, and show the interesting result that there exist families of two-stage fourth-order P-stable methods. We also obtain some families of three-stage fourth-order P-stable methods. The obtained methods are computationally tested on problems of practical interest.     

On new higher order families of simultaneous methods for finding polynomial zeros

Two one parameter families of iterative methods for the simultaneous determination of simple zeros of algebraic polynomials are presented. The construction of these families are based on a one parameter family of the third order for finding a single root of nonlinear equation f(x)=0. Some previously derived simultaneous methods can be obtained from the presented families as special cases. We prove that the local convergence of the proposed families is of the order four. Numerical results are included to demonstrate the convergence properties of considered methods.     

k-Interchange procedures for local search in a precedence-constrained routing problem

We develop k-interchange procedures to perform local search in a precedence-constrained routing problem. The problem in question is known in the Transportation literature as the single vehicle many-to-many Dial-A-Ride Problem, or DARP. The DARP is the problem of minimizing the length of the tour traveled by a vehicle to service N customers, each of whom wishes to go from a distinct origin to a distinct destination. The vehicle departs from a specified point and returns to that point upon service of all customers. Precedence constraints in the DARP exist because the origin of each customer must precede his/her destination on the route. As in the interchange procedure of Lin for the Traveling Salesman Problem (TSP), a k-interchange is a substitution of k of the links of an initial feasible DARP tour with k other links, and a DARP tour is k-optimal if it is impossible to obtain a shorter tour by replacing any k of its links by k other links. However, in contrast to the TSP where each individual interchange takes O(1) time, checking whether each individual DARP interchange satisfies the origin-destination precedence constraints normally requires O(N²) time. In this paper we develop a method which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(N^k) time, the same order of magnitude as in the Lin heuristic for the TSP. This method is then embedded in a breadth-first or a depth-first search procedure to produce a k-optimal DARP tour. The paper focuses on the k = 2 and k = 3 cases. Experience with the procedures is presented. in which k-optimal tours are produced by applying a 2-opt or 3-opt search to initial DARP tours produced either randomly or by a fast O(N²) heuristic. The breadth-first and depth-first search modes are compared. The heuristics are seen to produce very good or near-optimal DARP tours.     

Multiobjective traveling salesperson problem on Halin graphs

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.     

On the empirical scaling of running time for finding optimal solutions to the TSP

We study the empirical scaling of the running time required by state-of-the-art exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the finding time) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance; we also compare the resulting models to that for the scaling of Concorde’s finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.     

Compact formulations of the Steiner Traveling Salesman Problem and related problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the TSP that is particularly suitable when routing on real-life road networks. The standard integer programming formulations of both the TSP and STSP have an exponential number of constraints. On the other hand, several compact formulations of the TSP, i.e., formulations of polynomial size, are known. In this paper, we adapt some of them to the STSP, and compare them both theoretically and computationally. It turns out that, just by putting the best of the formulations into the CPLEX branch-and-bound solver, one can solve instances with over 200 nodes. We also briefly discuss the adaptation of our formulations to some related problems.     

On t-Covering Arrays

This paper concerns construction methods for t-covering arrays. Firstly, a construction method using perfect hash families is discussed by combining with recursion techniques and error-correcting codes. In particular, by using algebraic-geometric codes for this method we obtain infinite families of t-covering arrays which are proved to be better than currently known probabilistic bounds for covering arrays. Secondly, inspired from a result of Roux [16] and also from a recent result of Chateauneuf and Kreher [6] for 3-covering arrays, we present several explicit constructions for t-covering arrays, which can be viewed as generalizations of their results for t-covering arrays.     

A mono-implicit Runge-Kutta-Nyström modification of the Numerov method

We present two two-parameter families of fourth-order mono-implicit Runge-Kutta-Nyström methods. Each member of these families can be considered as a modification of the Numerov method. We analyze the stability and periodicity properties of these methods. It is shown that (i) within one of these families there exist A-stable (even L-stable) and P-stable methods, and (ii) in both families there exist methods with a phase lag of order six.     

On Schröder’s families of root-finding methods

Schröder’s methods of the first and second kind for solving a nonlinear equation f(x)=0, originally derived in 1870, are of great importance in the theory and practice of iteration processes. They were rediscovered several times and expressed in different forms during the last 130 years. It was proved in the paper of Petkovi? and Herceg (1999) [7] that even seven families of iteration methods for solving nonlinear equations are mutually equivalent. In this paper we show that these families are also equivalent to another four families of iteration methods and find that all of them have the origin in Schröder’s generalized method (of the second kind) presented in 1870. In the continuation we consider Smale’s open problem from 1994 about possible link between Schröder’s methods of the first and second kind and state the link in a simple way.     

Four-point conditions for the TSP: The complete complexity classification

The combinatorial optimization literature contains a multitude of polynomially solvable special cases of the traveling salesman problem (TSP) which result from imposing certain combinatorial restrictions on the underlying distance matrices. Many of these special cases have the form of so-called four-point conditions: inequalities that involve the distances between four arbitrary cities.In this paper we classify all possible four-point conditions for the TSP with respect to computational complexity, and we determine for each of them whether the resulting special case of the TSP can be solved in polynomial time or whether it remains NP-hard.     

Global dynamics of a mathematical model for HTLV-I infection of CD4 T cells with delayed CTL response

Human T-cell leukaemia virus type I (HTLV-I) preferentially infects the CD4⁺ T cells. The HTLV-I infection causes a strong HTLV-I specific immune response from CD8⁺ cytotoxic T cells (CTLs). The persistent cytotoxicity of the CTL is believed to contribute to the development of a progressive neurologic disease, HTLV-I associated myelopathy/tropical spastic paraparesis (HAM/TSP). We investigate the global dynamics of a mathematical model for the CTL response to HTLV-I infection in vivo. To account for a series of immunological events leading to the CTL response, we incorporate a time delay in the response term. Our mathematical analysis establishes that the global dynamics are determined by two threshold parameters R₀ and R₁, basic reproduction numbers for viral infection and for CTL response, respectively. If R₀≤1, the infection-free equilibrium P₀ is globally asymptotically stable, and the HTLV-I viruses are cleared. If R₁≤1<R₀, the asymptomatic-carrier equilibrium P₁ is globally asymptotically stable, and the HTLV-I infection becomes chronic but with no persistent CTL response. If R₁>1, a unique HAM/TSP equilibrium P₂ exists, at which the HTLV-I infection is chronic with a persistent CTL response. We show that the time delay can destabilize the HAM/TSP equilibrium, leading to Hopf bifurcations and stable periodic oscillations. Implications of our results to the pathogenesis of HTLV-I infection and HAM/TSP development are discussed.     

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.