  


On the generation of symmetry breaking constraints for mathematical programs
Leo Liberti(libertilix.polytechnique.fr) Abstract: Mathematical programs whose formulation is symmetric often take a long time to solve using BranchandBound 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. Keywords: Keywords: mathematical programming, static symmetry breaking, MILP, MINLP. Category 1: Integer Programming Citation: Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL 60439 July 2011 Download: [PDF] Entry Submitted: 07/15/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  