Branch-and-cut for symmetrical ILPs and combinatorial designs

Abstract

Many combinatorial problems can be formulated as a 0-1 integer linear program (0-1 ILP), which consists of an objective function subject to linear constraints over 0-1 variables. A method called branch-and-cut has been successfully used to attack ILPs, but ILPs are still difficult to solve in practice. The problems we investigate demonstrate large numbers of equivalent (isomorphic) solutions. We are only interested in generating one solution from each equivalence class. To accomplish this, we study and extend a method by Margot [22] that avoids con sidering unnecessary partial solutions by generating an isomorph-free search tree. We implement a branch-and-cut library, and solve combinatorial design problems involving t-designs, packings, coverings and intersecting set systems. We experimentally analyze the strengths and limitations of our algorithms and determine when it is efficient to use isomorph-free branch-and-cut. Our framework generates new results and reproduces, in competitive time, existing ones.