Mathematical programs whose formulation is symmetric often take a long time to solve using Branch-and-Bound type algorithms, because of the several symmetric optima. One of the techniques used to decrease the adverse effects of symmetry is adjoining symmetry breaking constraints to the formulation before solving the problem. These constraints aim to make some of the symmetric optima infeasible but guarantee that at least one optimum is feasible. Such constraints are usually associated to the different orbits of the action of the formulation group on the set of variable indices. In general, one cannot adjoin symmetry breaking constraints from more than one orbit. In previous work [14] we discussed some (restrictive) sufficient conditions for adjoining such constraints from several orbits. In this paper we present a new method for generating symmetry breaking constraints from several orbits. We show it is less restrictive than the existing method, and discuss some computational experiments.
Citation
Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL 60439 July 2011