A new integer programming formulation of the graphical traveling salesman problem

DOI10.1007/978-3-030-73879-2_32MaRDI QIDQ5918436zbMATH OpenOpenAlexFDO

Authors Robert D. Carr, Neil Simonetti

Publication date 21 December 2021

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.04933

zbMATH Keywords

graphical traveling salesman problemGTSPlinear programrelaxationtraveling salesman problemTSP

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost $c_{ij}$ of traveling from city $i$ to city $j$, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classes of constraints that are either polynomial in number or polynomially separable, while addressing an open question proposed by Denis Naddef.

Recommendations

• A new integer programming formulation of the graphical traveling salesman problem
• Models for Solving the Travelling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• A New Formulation for the Travelling Salesman Problem
• scientific article; zbMATH DE number 4143778

Cites work

• A cutting plane algorithm for the general routing problem
• A cutting plane procedure for the travelling salesman problem on road networks
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Compact extended linear programming models
• Compact formulations of the Steiner traveling salesman problem and related problems
• Compact vs. exponential-size LP relaxations
• Edge-Disjoint Spanning Trees of Finite Graphs
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 795217 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the Problem of Decomposing a Graph into n Connected Factors
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The traveling salesman problem and its variations.
• The traveling salesman problem on a graph and some related integer polyhedra
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(4)

• The graphical traveling salesperson problem has no integer programming formulation in the original space
• An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
• A New Formulation for the Travelling Salesman Problem
• A new integer programming formulation of the graphical traveling salesman problem

This page was built for publication: A new integer programming formulation of the graphical traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918436)