Packing and partitioning orbitopes
From MaRDI portal
Publication:925263
DOI10.1007/s10107-006-0081-5zbMath1171.90004arXivmath/0603678MaRDI QIDQ925263
Volker Kaibel, Marc E. Pfetsch
Publication date: 3 June 2008
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0603678
Integer programming; graph coloring; Symmetry breaking; Lexicographic representatives; packing polytopes; partitioning polytopes
52B12: Special polytopes (linear programming, centrally symmetric, etc.)
90C10: Integer programming
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27: Combinatorial optimization
Related Items
Automatic Generation of Symmetry-Breaking Constraints, Extended formulations in combinatorial optimization, Extended formulations in combinatorial optimization, Orbitopal fixing, A supernodal formulation of vertex colouring with applications in course timetabling, Orbital branching, Reformulations in mathematical programming: automatic symmetry detection and exploitation, The maximum \(k\)-colorable subgraph problem and orbitopes, Hard multidimensional multiple choice knapsack problems, an empirical study, Algorithms for highly symmetric linear and integer programs, Exploiting Symmetries in Polyhedral Computations, Symmetry in Mathematical Programming, Spherical cuts for integer programming problems, Constraint Orbital Branching
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cliques, holes and the vertex coloring polytope
- Geometric algorithms and combinatorial optimization.
- Pruning by isomorphism in branch-and-cut
- Small covering designs by branch-and-cut
- Symmetry breaking revisited
- Facets of the graph coloring polytope
- A branch-and-cut algorithm for graph coloring
- A Mathematical Model for Periodic Scheduling Problems
- Decomposing Matrices into Blocks
- A Column Generation Approach for Graph Coloring