An analytical comparison of different formulations of the travelling salesman problem

DOI10.1007/BF01582894zbMath0770.90075OpenAlexW1985322505MaRDI QIDQ1181739

Ting-Yi Sung, Manfred W. Padberg

Publication date: 27 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582894

zbMATH Keywords

affine transformationstransformation techniqueconvex polyhedral conesasymmetric travelling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items (38)

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Integer programming formulations for the elementary shortest path problem ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ An analytic symmetrization of max flow-min cut ⋮ Routing problems: A bibliography ⋮ Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope ⋮ A representation of an efficiency equivalent polyhedron for the objective set of a multiple objective linear program ⋮ A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem ⋮ A classification of formulations for the (time-dependent) traveling salesman problem ⋮ Tight lower bounds for the traveling salesman problem with draft limits ⋮ Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups ⋮ A polyhedral study of the diameter constrained minimum spanning tree problem ⋮ An investigation into two bin packing problems with ordering and orientation implications ⋮ An alternate formulation of the symmetric traveling salesman problem and its properties ⋮ Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ A comparative analysis of several asymmetric traveling salesman problem formulations ⋮ Formulations and valid inequalities for the heterogeneous vehicle routing problem ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Discrete relaxations of combinatorial programs ⋮ On pedigree polytopes and Hamiltonian cycles ⋮ On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem ⋮ Integer programming formulations for the \(k\)-in-a-tree problem in graphs ⋮ Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints ⋮ Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration ⋮ A combined constraint-space, objective-space approach for determining high-dimensional maximal efficient faces of multiple objective linear programs ⋮ The asymmetric traveling salesman problem with replenishment arcs ⋮ An extensible multi-block layout warehouse routing optimization model ⋮ Survey of facial results for the traveling salesman polytope ⋮ Projection results for vehicle routing ⋮ Approximate extended formulations ⋮ Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation ⋮ Compact formulations of the Steiner traveling salesman problem and related problems ⋮ Projection, lifting and extended formulation integer and combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The perfectly matchable subgraph polytope of an arbitrary graph
• A new polynomial-time algorithm for linear programming
• Strong formulations for mixed integer programming: A survey
• An analytic symmetrization of max flow-min cut
• Elementare Theorie der konvexen Polyeder
• The perfectly matchable subgraph polytope of a bipartite graph
• Über homogene lineare Ungleichungssysteme
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• On the width—length inequality
• A generalization of max flow—min cut
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach

This page was built for publication: An analytical comparison of different formulations of the travelling salesman problem