traveling salesman problem

Equivalence of an Approximate Linear Programming Bound with the Held-Karp Bound for the Traveling Salesman Problem

  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming Tags , , ,

    We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP’s arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP’s shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP’s optimal cost regardless … Read more

    Multidirectional Physarum Solver: an Innovative Bio-inspired Algorithm for Optimal Discrete Decision Making

  • Luca Masi
  • Massimiliano Vasile
    • Categories Combinatorial Optimization Tags , , , , ,

    This paper introduces a new bio-inspired algorithm for optimal discrete decision making, able to incrementally grow and explore decision graphs in multiple directions. The heuristic draws inspiration from the idea that building decision sequences from multiple directions and then combining the sequences is an optimal choice if compared with a unidirectional approach. The behaviour of … Read more

    An extended approach for lifting clique tree inequalities

  • Anja Fischer
  • Frank Fischer
    • Categories Combinatorial Optimization, Polyhedra Tags , ,

    We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling salesman problem (SQTSP). Applying this new approach to the subtour elimination constraints (SEC) leads to two new classes … Read more

    A Dynamic Traveling Salesman Problem with Stochastic Arc Costs

  • William Haskell
  • Alejandro Toriello
  • Michael Poremba
    • Categories Dynamic Programming, Semi-infinite Programming, Transportation Tags , , ,

    We propose a dynamic traveling salesman problem (TSP) with stochastic arc costs motivated by applications, such as dynamic vehicle routing, in which a decision’s cost is known only probabilistically beforehand but is revealed dynamically before the decision is executed. We formulate the problem as a dynamic program (DP) and compare it to static counterparts to … Read more

    Compact formulations of the Steiner traveling salesman problem and related problems

  • Adam N. Letchford
  • Saeideh Nasiri
  • Dirk Oliver Theis
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there … Read more

    Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem

  • Alejandro Toriello
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

    We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with diff erent 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 … Read more

    SDP relaxations for some combinatorial optimization problems

  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this chapter we present recent developments on solving various combinatorial optimization problems by using semidefinite programming (SDP). We present several SDP relaxations of the quadratic assignment problem and the traveling salesman problem. Further, we show the equivalence of several known SDP relaxations of the graph equipartition problem, and present recent results on the bandwidth … Read more

    Experimental analysis of heuristics for the bottleneck traveling salesman problem

  • Eric Aubanel
  • John LaRusic
  • Abraham Punnen
    • Categories Combinatorial Optimization Tags , , ,

    In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially … Read more

    A Comparison of Lower Bounds for the Symmetric Circulant Traveling Salesman Problem

  • Etienne de Klerk
  • Cristian Dobre
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    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 … Read more

    The Delivery Man Problem with Time Windows

  • Jean-François Cordeau
  • GĂ©raldine Heilporn
  • Gilbert Laporte
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results … Read more