A computational comparison of symmetry handling methods for mixed integer programs

DOI10.1007/s12532-018-0140-yzbMath1411.90233OpenAlexW2811231250WikidataQ129575088 ScholiaQ129575088MaRDI QIDQ1741126

Thomas Rehn, Marc E. Pfetsch

Publication date: 3 May 2019

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-018-0140-y

zbMATH Keywords

symmetrybranch-and-cutisomorphism pruningmixed integer programorbital branching

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Exploiting symmetries in mathematical programming via orbital independence, Equivalence of Lattice Orbit Polytopes, Polytopes associated with symmetry handling, Handling symmetries in mixed-integer semidefinite programs, Finding Symmetry Groups of Some Quadratic Programming Problems, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Exploiting symmetry in integer convex optimization using core points, Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem, Integer Programming for Classifying Orthogonal Arrays, On the geometry of symmetry breaking inequalities, Presolve Reductions in Mixed Integer Programming, Fundamental Domains for Symmetric Optimization: Construction and Search, Political districting to minimize cut edges

Uses Software

• GAP
• nauty
• SCIP
• MIPLIB
• MIPLIB2003
• PermLib
• Saucy
• bliss

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orbitopal fixing
• Stabilizer-based symmetry breaking constraints for mathematical programs
• Orbital branching
• Reformulations in mathematical programming: automatic symmetry detection and exploitation
• SCIP: solving constraint integer programs
• Packing and partitioning orbitopes
• Pruning by isomorphism in branch-and-cut
• Small covering designs by branch-and-cut
• Exploiting orbits in symmetric ILP
• Symmetry groups, semidefinite programs, and sums of squares
• Algorithms for highly symmetric linear and integer programs
• Conflict graphs in solving integer programming problems
• On lattice-free orbit polytopes
• Exploiting symmetry in integer convex optimization using core points
• MIPLIB 2003
• Conflict analysis in mixed integer programming
• Symmetric ILP: Coloring and small integers
• On solving a hard quadratic 3-dimensional assignment problem
• Computing symmetry groups of polyhedra
• Improving Discrete Model Representations via Symmetry Considerations
• Orbital Shrinking
• Extended Formulations for Packing and Partitioning Orbitopes
• Automatic Detection of Variable and Value Symmetries
• Fundamental Domains for Integer Programs with Symmetries
• The graph isomorphism disease
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Orbital Shrinking: A New Tool for Hybrid MIP/CP Methods
• The NP-completeness column
• Facets and Rank of Integer Polyhedra
• Detecting Orbitopal Symmetries
• Orbital Branching
• Automatic Generation of Symmetry-Breaking Constraints