A new integer programming formulation of the graphical traveling salesman problem

DOI10.1007/978-3-030-73879-2_32zbMath1483.90132arXiv2006.04933OpenAlexW3165561263MaRDI QIDQ5918436

Neil Simonetti, Robert D. Carr

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

TSPrelaxationtraveling salesman problemlinear programGTSPgraphical traveling salesman problem

Mathematics Subject Classification ID

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

Related Items (1)

The graphical traveling salesperson problem has no integer programming formulation in the original space

Cites Work

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

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