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
- 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?)
- 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
- 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
(39)- A unified framework for symmetry handling
- Parity polytopes and binarization
- Large-scale unit commitment under uncertainty: an updated literature survey
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Orbitopal Fixing
- Detecting orbitopal symmetries
- Last fifty years of integer linear programming: a focus on recent practical advances
- The power of optimization over randomization in designing experiments involving small samples
- 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
- The maximum k-colorable subgraph problem and orbitopes
- A two-level graph partitioning problem arising in mobile wireless communications
- An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints
- Packing and partitioning orbitopes
- The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
- Constraint Orbital Branching
- Polytopes associated with symmetry handling
- Orbital branching
- Modified orbital branching for structured symmetry with an application to unit commitment
- Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs
- Symmetry detection in mixed-integer conic programming
- Detecting and handling reflection symmetries in mixed-integer (nonlinear) programming and beyond
- Orbital Branching
- Projection results for the \(k\)-partition problem
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
- Convex hull characterizations of lexicographic orderings
- Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
- Lexicographical order in integer programming
- Exploiting sparsity for the min \(k\)-partition problem
- An exact approach for the multi-constraint graph partitioning problem
- Handling sub-symmetry in integer programming using activation handlers
- Packing, partitioning, and covering symresacks
- Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
- Mixed-integer programming techniques for the minimum sum-of-squares clustering problem
- Extended formulations for packing and partitioning orbitopes
- Complexity, algorithmic, and computational aspects of a dial-a-ride type problem
- Optimization for Power Systems and the Smart Grid
- Political districting to minimize cut edges
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)
