Combinatorial optimization and small polytopes (Q1814809)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Combinatorial optimization and small polytopes
scientific article

    Statements

    Combinatorial optimization and small polytopes (English)
    0 references
    0 references
    0 references
    23 March 1997
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    special polytopes
    0 references
    double-description method
    0 references
    computational geometry
    0 references
    hard combinatorial optimization
    0 references
    branch-and-cut method
    0 references
    facet structure
    0 references
    traveling salesman
    0 references
    linear ordering polytopes
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references