Packing and partitioning orbitopes

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

zbMATH Keywords

Integer programming; graph coloring; Symmetry breaking; Lexicographic representatives; packing polytopes; partitioning polytopes

Mathematics Subject Classification ID

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

Equivalence of Lattice Orbit Polytopes, Optimization for Power Systems and the Smart Grid, Automatic Generation of Symmetry-Breaking Constraints, Extended formulations in combinatorial optimization, Extended formulations in combinatorial optimization, A polyhedral investigation of star colorings, Convex hull characterizations of lexicographic orderings, Discrete optimization methods to fit piecewise affine models to data points, 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, On Dantzig figures from graded lexicographic orders, Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions, Algorithms for highly symmetric linear and integer programs, Modified orbital branching for structured symmetry with an application to unit commitment, Lexicographical order in integer programming, A polyhedral approach for the equitable coloring problem, Employee workload balancing by graph partitioning, Exploiting symmetry in integer convex optimization using core points, Exploiting Symmetries in Polyhedral Computations, Symmetry in Mathematical Programming, Orbital Independence in Symmetric Mathematical Programs, Spherical cuts for integer programming problems, Constraint Orbital Branching

Uses Software

• PESPLib

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