Abstract: We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case both the description and the proof are more involved. Nevertheless, the associated separation problem can be solved in linear time also in this case.
Recommendations
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2084699 (Why is no real title available?)
- A Column Generation Approach for Graph Coloring
- A Mathematical Model for Periodic Scheduling Problems
- A branch-and-cut algorithm for graph coloring
- A polyhedral approach for graph coloring
- Breaking instance-independent symmetries in exact graph coloring
- Cliques, holes and the vertex coloring polytope
- Decomposing Matrices into Blocks
- Facets of the graph coloring polytope
- Geometric algorithms and combinatorial optimization.
- Models for line planning in public transport
- Pruning by isomorphism in branch-and-cut
- Small covering designs by branch-and-cut
- Symmetry breaking revisited
Cited in
(49)- Modified orbital branching for structured symmetry with an application to unit commitment
- Employee workload balancing by graph partitioning
- An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
- Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem
- The maximum \(k\)-colorable subgraph problem and orbitopes
- Discrete optimization methods to fit piecewise affine models to data points
- Exploiting symmetries in mathematical programming via orbital independence
- A branch-and-cut algorithm for the connected max-\(k\)-cut problem
- Reformulations in mathematical programming: automatic symmetry detection and exploitation
- Orbital branching
- Exploiting symmetries in polyhedral computations
- A polyhedral investigation of star colorings
- Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
- On the combinatorics of the 2-class classification problem
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Matrices with lexicographically-ordered rows
- Symmetry-breaking inequalities for ILP with structured sub-symmetry
- Extended formulations for packing and partitioning orbitopes
- Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs
- Orbitopal fixing
- Extended formulations in combinatorial optimization
- Constraint Orbital Branching
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Symmetry in mathematical programming
- Political districting to minimize cut edges
- Describing orbitopes by linear inequalities and projection based tools.
- Equivalence of lattice orbit polytopes
- Mixed-integer programming techniques for the minimum sum-of-squares clustering problem
- Fundamental domains for symmetric optimization: construction and search
- Lexicographical order in integer programming
- Spherical cuts for integer programming problems
- Packing, partitioning, and covering symresacks
- Exploiting symmetry in integer convex optimization using core points
- Optimization for Power Systems and the Smart Grid
- Hard multidimensional multiple choice knapsack problems, an empirical study
- Polytopes associated with symmetry handling
- On Dantzig figures from graded lexicographic orders
- Strong IP formulations need large coefficients
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Extended formulations in combinatorial optimization
- Orbital independence in symmetric mathematical programs
- Convex hull characterizations of lexicographic orderings
- Algorithms for highly symmetric linear and integer programs
- A supernodal formulation of vertex colouring with applications in course timetabling
- A polyhedral approach for the equitable coloring problem
- Automatic Generation of Symmetry-Breaking Constraints
- On the geometry of symmetry breaking inequalities
- A computational comparison of symmetry handling methods for mixed integer programs
- On the geometry of symmetry breaking inequalities
This page was built for publication: Packing and partitioning orbitopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q925263)
