Reformulations in Mathematical Programming: Symmetry

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 automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so that some symmetric solutions become infeasible. The reformulated problem can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and {\sc Couenne} (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib and MINLPLib 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.

Article

Download

View PDF