Symmetric ILP: Coloring and small integers

DOI10.1016/J.DISOPT.2006.10.008zbMath1169.90411OpenAlexW1970944326MaRDI QIDQ2471273

Margot, François

Publication date: 22 February 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.10.008

zbMATH Keywords

symmetrybranch-and-cutisomorphism pruning

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (17)

Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems ⋮ Symmetry in Mathematical Programming ⋮ Finding the dimension of a non-empty orthogonal array polytope ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ Polytopes associated with symmetry handling ⋮ Total coloring and total matching: polyhedra and facets ⋮ Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays ⋮ Orbitopal fixing ⋮ Reformulations in mathematical programming: automatic symmetry detection and exploitation ⋮ The maximum \(k\)-colorable subgraph problem and orbitopes ⋮ A computational comparison of symmetry handling methods for mixed integer programs ⋮ Classification of orthogonal arrays by integer programming ⋮ The linear programming relaxation permutation symmetry group of an orthogonal array defining integer linear program ⋮ Integer Programming for Classifying Orthogonal Arrays ⋮ Automatic Generation of Symmetry-Breaking Constraints ⋮ Political districting to minimize cut edges ⋮ Algorithms for finding generalized minimum aberration designs

Uses Software

• ABACUS
• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general backtrack algorithm for the isomorphism problem of combinatorial objects
• Group-theoretic algorithms and graph isomorphism
• Fundamental algorithms for permutation groups
• Orthogonal arrays. Theory and applications
• Pruning by isomorphism in branch-and-cut
• Exploiting orbits in symmetric ILP
• Classification of orthogonal arrays by integer programming
• Regular \(n\)-valent \(n\)-connected non-Hamiltonian non \(n\)-edge-colourable graphs
• The rise and fall of the critical graph conjecture
• Computing in Permutation and Matrix Groups I: Normal Closure, Commutator Subgroups, Series
• Computing in Permutation and Matrix Groups II: Backtrack Algorithm
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• On the Value of Binary Expansions for General Mixed-Integer Linear Programs
• On an Algorithm for Finding a Base and a Strong Generating Set for a Group Given by Generating Permutations
• Isomorph-Free Exhaustive Generation
• Computational combinatorial optimization. Optimal of probably near-optimal solutions

This page was built for publication: Symmetric ILP: Coloring and small integers