Isomorphism in Branch-and-Cut
Francois Margot, Visiting Scholar, GSIA
Oct 24, 2003, Posner 152, 3:30--5pm

Abstract:

With recent advances in cutting techniques, Branch-and-Cut has become the method of choice for solving (0, 1) integer linear programs (ILP). Yet, certain classes of problems remain difficult to solve, despite having relatively small size. For example, many problems in combinatorics ask for a family of subsets of a given set $S$ with certain properties. Graph coloring is an other typical example. These problems usually lead to difficult ILP. A common feature of these problems is the presence of symmetries: All elements of the set $S$ are equivalent, implying that several symmetric optimal solutions exists, all colors are equivalent and can be permuted. Exploiting the knowledge of the symmetry group of the problem, it is possible to improve dramatically the performances of a Branch-and-Cut by detecting isomorphism between subproblems and pruning all but one in each isomorphism class.

We show how to perform this isomorphism pruning with backtracking procedures based on a Schreier-Sims representation of the symmetry group. We also show how to use the symmetry group to generate cuts and set variables. Applications to the generation of covering designs, error correcting codes, and a class of hard set covering problems are presented.

Keywords: Branch-and-Cut, isomorphism, group operations.