Reformulations in mathematical programming: Symmetry

Tuesday, November 18, 2008 - 2:45pm - 3:30pm
EE/CS 3-180
Leo Liberti (École Polytechnique)
If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for: (a) automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and (b) reformulating the problem so that it has fewer symmetric solutions. The reformulated problem can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and Couenne (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib, MINLPLib and MacMINLP instance libraries, solution tables for some instances in the aforementioned libraries, and a theoretical and computational study of the symmetries of the Kissing Number Problem.
MSC Code: