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