Algorithmic Aspects of Using Small Instance Relaxations in Parallel Branch-and-Cut

Abstract.

Essential for the success of branch-and-cut algorithms for solving combinatorial optimization problems are the availability of reasonable tight relaxations and effective routines for solving the associated separation problems. In this paper we introduce the concept of small instance relaxations which can be particularly useful for problems with symmetric structure. Small instance relaxations are based on the facets of polytopes associated with small instances of the combinatorial optimization problem to be solved and can be generated automatically by facet enumeration. For a certain class of symmetric problems, we describe a general approach to the separation problem. Algorithmic aspects of using small instance relaxations effectively (parallel separation, facet selection, cutting plane selection) are discussed in detail. Extensive computational results are presented for the linear ordering problem and a certain betweenness problem.