On the symmetric travelling salesman problem II: Lifting theorems and facets
From MaRDI portal
Publication:3048581
DOI10.1007/BF01582117zbMath0413.90049OpenAlexW1540760152MaRDI QIDQ3048581
Manfred W. Padberg, Martin Grötschel
Publication date: 1979
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582117
integer programmingtraveling salesman problemconvex polytopeslinear inequalitiesfacetslifting theorems
Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Polytopes and polyhedra (52Bxx)
Related Items
Clique tree inequalities define facets of the asymmetric traveling salesman polytope, On the magnetisation of the ground states in two dimensional Ising spin glasses, Separation, dimension, and facet algorithms for node flow polyhedra, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, The complexity of facets resolved, A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, On cutting-plane proofs in combinatorial optimization, Polyhedral Combinatorics in Combinatorial Optimization, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, The time dependent traveling salesman problem: polyhedra and algorithm, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, The symmetric quadratic traveling salesman problem, Facet Generating Techniques, Facet identification for the symmetric traveling salesman polytope, An extended approach for lifting clique tree inequalities, On the Chvátal-Gomory Closure of a Compact Convex Set, Separating maximally violated comb inequalities in planar graphs, George Dantzig's contributions to integer programming, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Polarity and the complexity of the shooting experiment, A New Formulation for the Travelling Salesman Problem, On the \({\mathcal {H}}\)-free extension complexity of the TSP, On the Chvátal-Gomory closure of a compact convex set, On the symmetric travelling salesman problem I: Inequalities, On the domino-parity inequalities for the STSP, Minimum-weight two-connected spanning networks, A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem, 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, Facets and algorithms for capacitated lot sizing, Recent trends in combinatorial optimization, 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 complexity of facets (and some facets of complexity), Survey of facial results for the traveling salesman polytope, Optimizing over the subtour polytope of the travelling salesman problem, Solution of large-scale symmetric travelling salesman problems, Light on the infinite group relaxation. I: Foundations and taxonomy
Cites Work
