Optimization Online


A Computational Comparison of Symmetry Handling Methods for Mixed Integer Programs

Marc E. Pfetsch (pfetsch***at***opt.tu-darmstadt.de)
Thomas Rehn (thomas.rehn***at***research.initos.com)

Abstract: The handling of symmetries in mixed integer programs in order to speed up the solution process of branch-and-cut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present in the MIPLIB 2010 instances. It turns out that many instances are affected by symmetry and most symmetry groups contain full symmetric groups as factors. We then present (variants of) six symmetry handling methods from the literature. Their implementation is tested on several testsets. On very symmetric instances used previously in the literature, it is essential to use methods like isomorphism pruning, orbital fixing, or orbital branching. Moreover, tests on the MIPLIB instances show that isomorphism pruning, orbital fixing, or adding symmetry breaking inequalities allow to speed-up the solution process by about 15 % and more instances can be solved within the time limit.

Keywords: symmetry, mixed-integer program, branch-and-cut, ismorphism pruning, orbital branching

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 11/21/2015
Entry Accepted: 11/21/2015
Entry Last Modified: 11/22/2015

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