Packing and partitioning orbitopes
From MaRDI portal
Publication:925263
DOI10.1007/S10107-006-0081-5zbMATH Open1171.90004arXivmath/0603678OpenAlexW2074723965MaRDI QIDQ925263FDOQ925263
Marc E. Pfetsch, Volker Kaibel
Publication date: 3 June 2008
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/0603678
graph coloringInteger programmingSymmetry breakingLexicographic representativespacking polytopespartitioning polytopes
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- A Mathematical Model for Periodic Scheduling Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization.
- Decomposing Matrices into Blocks
- Facets of the graph coloring polytope
- A branch-and-cut algorithm for graph coloring
- Title not available (Why is that?)
- A Column Generation Approach for Graph Coloring
- Cliques, holes and the vertex coloring polytope
- Pruning by isomorphism in branch-and-cut
- Small covering designs by branch-and-cut
- Symmetry breaking revisited
- Title not available (Why is that?)
- A polyhedral approach for graph coloring
- Title not available (Why is that?)
Cited In (47)
- Symmetry in Mathematical Programming
- A polyhedral approach for the equitable coloring problem
- Exploiting symmetries in mathematical programming via orbital independence
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Extended formulations in combinatorial optimization
- Spherical cuts for integer programming problems
- A polyhedral investigation of star colorings
- On Dantzig figures from graded lexicographic orders
- Algorithms for highly symmetric linear and integer programs
- Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem
- A computational comparison of symmetry handling methods for mixed integer programs
- Exploiting Symmetries in Polyhedral Computations
- Strong IP formulations need large coefficients
- An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
- The maximum \(k\)-colorable subgraph problem and orbitopes
- Exploiting symmetry in integer convex optimization using core points
- Fundamental Domains for Symmetric Optimization: Construction and Search
- On the combinatorics of the 2-class classification problem
- Constraint Orbital Branching
- Polytopes associated with symmetry handling
- Orbital branching
- Modified orbital branching for structured symmetry with an application to unit commitment
- A branch-and-cut algorithm for the connected max-\(k\)-cut problem
- Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs
- Extended formulations in combinatorial optimization
- A supernodal formulation of vertex colouring with applications in course timetabling
- Employee workload balancing by graph partitioning
- Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
- Orbitopal fixing
- Convex hull characterizations of lexicographic orderings
- Reformulations in mathematical programming: automatic symmetry detection and exploitation
- Lexicographical order in integer programming
- Hard multidimensional multiple choice knapsack problems, an empirical study
- On the geometry of symmetry breaking inequalities
- On the geometry of symmetry breaking inequalities
- Orbital Independence in Symmetric Mathematical Programs
- Discrete optimization methods to fit piecewise affine models to data points
- Automatic Generation of Symmetry-Breaking Constraints
- Equivalence of Lattice Orbit Polytopes
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Packing, partitioning, and covering symresacks
- Mixed-integer programming techniques for the minimum sum-of-squares clustering problem
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Symmetry-breaking inequalities for ILP with structured sub-symmetry
- Optimization for Power Systems and the Smart Grid
- Matrices with lexicographically-ordered rows
- Political districting to minimize cut edges
Uses Software
Recommendations
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)
