Combinatorial optimization and small polytopes
From MaRDI portal
Publication:1814809
DOI10.1007/BF02568602zbMath0858.90107OpenAlexW2037314270MaRDI QIDQ1814809
Gerhard Reinelt, Thomas Christof
Publication date: 23 March 1997
Published in: Top (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02568602
traveling salesmancomputational geometrylinear ordering polytopesspecial polytopesbranch-and-cut methoddouble-description methodfacet structurehard combinatorial optimization
Exact enumeration problems, generating functions (05A15) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)
Related Items
A survey on the linear ordering problem for weighted or unweighted tournaments, On the graphical relaxation of the symmetric traveling salesman polytope, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, PANDA: a software for polyhedral transformations, A benchmark library and a comparison of heuristic methods for the linear ordering problem, Combinatorial integral approximation, A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments, Generating partitions of a graph into a fixed number of minimum weight cuts, Extended formulations for order polytopes through network flows, The hypermetric cone and polytope on eight vertices and some generalizations, An updated survey on the linear ordering problem for weighted or unweighted tournaments, DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES, Complexity and algorithms for computing Voronoi cells of lattices, Primary facets of order polytopes, PORTA, Exploiting Symmetries in Polyhedral Computations, Quasi-semi-metrics, oriented multi-cuts and related polyhedra, On the facial structure of symmetric and graphical traveling salesman polyhedra, Classification of eight-dimensional perfect forms
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Facet identification for the symmetric traveling salesman polytope
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Geometric and combinatorial properties of the polytope of binary choice probabilities
- A complete description of the traveling salesman polytope on 8 nodes
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Geometric algorithms and combinatorial optimization
- Introduction to ABACUS -- a branch-and-cut system
- More facets from fences for linear ordering and acyclic subgraph polytopes
- The graphical relaxation: A new framework for the symmetric traveling salesman polytope
- Hamiltonian path and symmetric travelling salesman polytopes
- Linear optimization and extensions
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A note on small linear-ordering polytopes
- Fourier-Motzkin elimination and its dual
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Über homogene lineare Ungleichungssysteme
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Facets of the linear ordering polytope
- Solving matching problems with linear programming
- A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
- Small Travelling Salesman Polytopes
- TSPLIB—A Traveling Salesman Problem Library
- The Crown Inequalities for the Symmetric Traveling Salesman Polytope
- Technical Note—Vertex Generation and Cardinality Constrained Linear Programs
- The General Solution of a Finite System of Linear Inequalities
- A LIBRARY FOR DOING POLYHEDRAL OPERATIONS
- Provably good solutions for the traveling salesman problem
- Maximum matching and a polyhedron with 0,1-vertices
- Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities
- Binary Probabilities Induced by Rankings
