Symmetric ILP: Coloring and small integers

DOI10.1016/J.DISOPT.2006.10.008MaRDI QIDQ2471273zbMATH OpenOpenAlexFDO

Authors François Margot

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

branch-and-cutisomorphism pruningsymmetry

Mathematics Subject Classification ID

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

Recommendations

• Symmetry in integer linear programming
• Symmetries in binary programs. A polyhedral perspective
• Exploiting orbits in symmetric ILP
• Algorithms for highly symmetric linear and integer programs
• Symmetry-breaking inequalities for ILP with structured sub-symmetry

Cites work

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

Cited in

(21)

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

Describes a project that uses

Uses Software

• ABACUS
• CPLEX

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2471273)