Symmetry in mathematical programming
Leo Liberti, CNRS LIX, Ecole Polytechnique, F-91128 Palaiseau, France


The most common method for finding guaranteed global optima of mathematical programs (either linear or nonlinear, whether involving integer variables or not) is the Branch-and-Bound (BB) algorithm. 

There exist reliable implementations of BB for Mixed-Integer Linear Programs (MILPs); for Mixed-Integer Nonlinear Programs (MINLPs) the situation is not as advanced, but there are nonetheless some implementations that can be used profitably. Of course there are many factors that impact the performance of a BB algorithm, the main ones being the bound quality and branching strategy. 

Symmetries in the solution space can adversely impact the quality of the bound, especially in lower BB search tree levels. If a given problem has many symmetric optima, many leaf nodes in the BB tree will contain optimal solutions, which means that the BB algorithm will never be able to prune the branches leading to these leaves. As a consequence, the BB tree exploration will yield trees of disproportionat sizes. If it were possible to detect symmetries before the solution process, we might then attempt to adjoin constraints eliminating some symmetric solutions whilst guaranteeing that at least one optimum is kept. Such constraints provide a reformulation of the narrowing type. In recent research we presented general techniques, applicable to MILPs and MINLPs, to find subgroups of the group of solutions of a mathematical program (previous related research was limited to MILPs and SDPs. 

In this abstract we briefly recount the main definitions and relate on computational experience on some applications (Kissing Number Problem, Circle Packing, and Minimum Fundamental Cycle Bases).