Combinatorial optimization and small polytopes
type: Item
instance of: scholarly article
title: Combinatorial optimization and small polytopes
zbMATH Open document ID: 0858.90107
DOI: 10.1007/BF02568602
published in: Top
publication date: 1997-03-23T00:00:00Z
review text: For many hard combinatorial optimization problems, the branch-and-cut method is the method of choice when trying to solve problem instances to optimality. Branch-and-cut algorithms are special branch-and-bound algorithms where the bounding is achieved by solving suitable linear programming relaxations. These linear programming relaxations are based on linear descriptions of certain polytopes which are associated with the combinatorial optimization problem to be solved. In this paper, we focus on a new approach for obtaining better linear programming relaxations which is based on the automatic derivation of complete or partial linear descriptions of polytopes associated with small problem instances. After a short introduction to the principles of cutting plane, resp. branch-and-cut algorithms, we describe the principal ideas of how to compute complete descriptions of combinatorial polytopes or at least to obtain information about their facet structure. We introduce the publicly available software package PORTA that we developed to obtain results with the help of the computer. Furthermore, we discuss linear descriptions of small instances of the traveling salesman and linear ordering polytopes in more detail. Facets of small problem instances are not only of theoretical interest. We show how to utilize these facets for practical problem solving within branch-and-cut algorithms. Special emphasis is given to the implementation of separation procedures on parallel hardware. Computational results are presented as well.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 940803
zbMATH Keywords: special polytopes
zbMATH Keywords: double-description method
zbMATH Keywords: computational geometry
zbMATH Keywords: hard combinatorial optimization
zbMATH Keywords: branch-and-cut method
zbMATH Keywords: facet structure
zbMATH Keywords: traveling salesman
zbMATH Keywords: linear ordering polytopes
author: Thomas Christof
author: Gerhard Reinelt
describes a project that uses: LOLIB
describes a project that uses: cdd
describes a project that uses: TSPLIB
describes a project that uses: ABACUS
describes a project that uses: PolyLib
MaRDI profile type: Publication
cites work: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: Small Travelling Salesman Polytopes
cites work: Über homogene lineare Ungleichungssysteme
cites work: Q5586522
cites work: Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities
cites work: A complete description of the traveling salesman polytope on 8 nodes
cites work: Fourier-Motzkin elimination and its dual
cites work: Q4133398
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q3772828
cites work: Binary Probabilities Induced by Rankings
cites work: The General Solution of a Finite System of Linear Inequalities
cites work: Q5645210
cites work: Solving matching problems with linear programming
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: Facets of the linear ordering polytope
cites work: Geometric algorithms and combinatorial optimization
cites work: Q3714900
cites work: Q4845366
cites work: Provably good solutions for the traveling salesman problem
cites work: Q4840772
cites work: Optimization by Simulated Annealing
cites work: More facets from fences for linear ordering and acyclic subgraph polytopes
cites work: A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
cites work: Q5817857
cites work: Q4234162
cites work: The Crown Inequalities for the Symmetric Traveling Salesman Polytope
cites work: The graphical relaxation: A new framework for the symmetric traveling salesman polytope
cites work: Linear optimization and extensions
cites work: Optimization of a 532-city symmetric traveling salesman problem by branch and cut
cites work: Facet identification for the symmetric traveling salesman polytope
cites work: A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
cites work: Q3682240
cites work: Hamiltonian path and symmetric travelling salesman polytopes
cites work: Q3680289
cites work: TSPLIB—A Traveling Salesman Problem Library
cites work: A note on small linear-ordering polytopes
cites work: Technical Note—Vertex Generation and Cardinality Constrained Linear Programs
cites work: Q3818127
cites work: Geometric and combinatorial properties of the polytope of binary choice probabilities
cites work: Introduction to ABACUS -- a branch-and-cut system
cites work: A LIBRARY FOR DOING POLYHEDRAL OPERATIONS
full work available at URL: https://doi.org/10.1007/bf02568602
OpenAlex ID: W2037314270
description: scientific article; zbMATH DE number 940803