On the symmetric travelling salesman problem I: Inequalities

DOI10.1007/BF01582116zbMath0413.90048MaRDI QIDQ3048580

Manfred W. Padberg, Martin Grötschel

Publication date: 1979

Published in: Mathematical Programming (Search for Journal in Brave)

integer programming combinatorial inequalities general comb in a graph hard combinatorial optimization problem symmetric n-city traveling salesman problem

Mathematics Subject Classification ID

Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Polytopes and polyhedra (52Bxx)

Related Items

Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm, Clique tree inequalities define facets of the asymmetric traveling salesman polytope, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), A branch-and-cut framework for the consistent traveling salesman problem, New techniques for cost sharing in combinatorial optimization games, A branch-and-cut algorithm for the preemptive swapping problem, The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach, A new class of cutting planes for the symmetric travelling salesman problem, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks, Multi-depot multiple TSP: a polyhedral study and computational results, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, On cutting-plane proofs in combinatorial optimization, On the graphical relaxation of the symmetric traveling salesman polytope, A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program, Polyhedral Combinatorics in Combinatorial Optimization, On the membership problem for the \({0, 1/2}\)-closure, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, The solution of some 100-city travelling salesman problems, The symmetric quadratic traveling salesman problem, Facet Generating Techniques, On minimal Eulerian graphs, Chvátal closures for mixed integer programming problems, Recent advances in vehicle routing exact algorithms, Polyhedral results for a vehicle routing problem, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, Classical cuts for mixed-integer programming and branch-and-cut, An extended approach for lifting clique tree inequalities, On the Chvátal-Gomory Closure of a Compact Convex Set, On the Circuit Diameter of Some Combinatorial Polytopes, On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms, Separating maximally violated comb inequalities in planar graphs, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Local search inequalities, On the Chvátal-Gomory closure of a compact convex set, Polyhedral study of the capacitated vehicle routing problem, On symmetric subtour problems, A combinatorial approach to nonlocality and contextuality, Exact algorithms for routing problems under vehicle capacity constraints, On the symmetric travelling salesman problem II: Lifting theorems and facets, A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants, On the domino-parity inequalities for the STSP, Minimum-weight two-connected spanning networks, Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure, Certification of an optimal TSP tour through 85,900 cities, A computational comparison of flow formulations for the capacitated location-routing problem, The skeleton of the symmetric Traveling Salesman Polytope, Galois connections for phylogenetic networks and their polytopes, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, A new integer programming formulation of the graphical traveling salesman problem, The general routing polyhedron: A unifying framework, A spectral approach to polyhedral dimension, Polyhedral techniques in combinatorial optimization I: Theory, Path planning for unmanned vehicles with localization constraints, Facets and algorithms for capacitated lot sizing, The optimum assignments and a new heuristic approach for the traveling salesman problem, On the facial structure of symmetric and graphical traveling salesman polyhedra, The 2-edge-connected subgraph polyhedron, The traveling salesman problem on a graph and some related integer polyhedra, Survey of facial results for the traveling salesman polytope, Some facets of the simple plant location polytope, Optimizing over the subtour polytope of the travelling salesman problem, Solution of large-scale symmetric travelling salesman problems, \(K_ i\)-covers. I: Complexity and polytopes, A cutting plane procedure for the travelling salesman problem on road networks, Light on the infinite group relaxation. I: Foundations and taxonomy

Cites Work