Optimization Online


On the generation of symmetry breaking constraints for mathematical programs

Leo Liberti(liberti***at***lix.polytechnique.fr)
James Ostrowski(jostrowski***at***anl.gov)

Abstract: 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.

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
Entry Accepted: 07/15/2011
Entry Last Modified: 07/15/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society