Combinatorial optimization and small polytopes (Q1814809)

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.