Solving Symmetric Integer Programs

We will discuss two mechanisms for dealing with integer programs that contain a great deal of symmetry—orbital branching and isomorphism pruning. These methods use information encoded in the symmetry group of the integer program to guide the branching decision and prune nodes of the search tree. Orbital branching and isomorphism pruning will be compared, and we will quickly introduce an extension that demonstrates how to combine the two.

We will finish by describing how isomorphism pruning was combined with a variety of enumerative techniques to attempt to tackle the “football pool problem”, a famous open problem in coding theory which asks the cardinality of the smallest covering code of the space {0,1,2}^6. With our approach, lower bounds on the size of an optimal code have been improved from 65 to 71. Sharpening this bound has required decades of CPU time on a computational grid consisting of thousands of non-dedicated CPUs.

Joint work with James Ostrowski, Fabrizio Rossi, Stefano Smriglio, Francois Margot, and Greg Thain