Orbitopal fixing
From MaRDI portal
Abstract: The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant, since this kind of symmetry unnecessarily blows up the search tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the search tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been introduced bei Kaibel and Pfetsch (Math. Programm. A, 114 (2008), 1-36). It does, however, not explicitly add inequalities to the model. Instead, it uses certain fixing rules for variables. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem.
Recommendations
Cites work
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- A computational study of graph partitioning
- A cutting plane algorithm for a clustering problem
- Cliques and clustering: A combinatorial approach
- Clustering of microarray data via clique partitioning
- Conflict analysis in mixed integer programming
- Constraint Orbital Branching
- Exploiting orbits in symmetric ILP
- Extended formulations for packing and partitioning orbitopes
- Facets of the \(k\)-partition polytope
- Facets of the clique partitioning polytope
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- Fundamental Domains for Integer Programs with Symmetries
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 1312992 (Why is no real title available?)
- scientific article; zbMATH DE number 2084699 (Why is no real title available?)
- scientific article; zbMATH DE number 2086928 (Why is no real title available?)
- Orbital branching
- Orbitopal Fixing
- Packing and partitioning orbitopes
- Principles of Constraint Programming
- Pruning by isomorphism in branch-and-cut
- SCIP: solving constraint integer programs
- Small covering designs by branch-and-cut
- Symmetric ILP: Coloring and small integers
- Symmetry breaking revisited
- Symmetry in integer linear programming
- The node capacitated graph partitioning problem: A computational study
- The partition problem
Cited in
(41)- Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs
- Large-scale unit commitment under uncertainty: an updated literature survey
- A computational comparison of symmetry handling methods for mixed integer programs
- A two-level graph partitioning problem arising in mobile wireless communications
- Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
- Projection results for the \(k\)-partition problem
- Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
- Political districting to minimize cut edges
- Exploiting sparsity for the min \(k\)-partition problem
- Packing, partitioning, and covering symresacks
- An exact approach for the multi-constraint graph partitioning problem
- Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Parity polytopes and binarization
- Modified orbital branching for structured symmetry with an application to unit commitment
- Lexicographical order in integer programming
- Polytopes associated with symmetry handling
- Extended formulations for packing and partitioning orbitopes
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Convex hull characterizations of lexicographic orderings
- Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
- The power of optimization over randomization in designing experiments involving small samples
- Constraint Orbital Branching
- Optimization for Power Systems and the Smart Grid
- Detecting orbitopal symmetries
- Orbitopal Fixing
- Orbital Branching
- The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Mixed-integer programming techniques for the minimum sum-of-squares clustering problem
- An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
- Orbital branching
- The maximum k-colorable subgraph problem and orbitopes
- Handling sub-symmetry in integer programming using activation handlers
- A unified framework for symmetry handling
- Last fifty years of integer linear programming: a focus on recent practical advances
- Symmetry detection in mixed-integer conic programming
- Detecting and handling reflection symmetries in mixed-integer (nonlinear) programming and beyond
- A framework for handling and exploiting symmetry in Benders decomposition
- Structure-preserving symmetry presolving for mixed-binary linear problems
- Packing and partitioning orbitopes
This page was built for publication: Orbitopal fixing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408377)
