SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Solving Symmetric Integer Programs

Jeff Linderoth, Prof.

Date and Time: Mar 05, 2014 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

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