Partial hyperplane activation for generalized intersection cuts
From MaRDI portal
Publication:2175444
Abstract: The generalized intersection cut (GIC) paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure called partial hyperplane activation (PHA), introduce a variant of PHA based on a notion of hyperplane tilting, and prove the validity of both algorithms. We propose several implementation strategies and parameter choices for our PHA algorithms and provide supporting theoretical results. We computationally evaluate these ideas in the COIN-OR framework on MIPLIB instances. Our findings shed light on the the strengths of the PHA approach as well as suggest properties related to strong cuts that can be targeted in the future.
Recommendations
- Generalized intersection cuts and a new cut generating paradigm
- Cutting hyperplanes for divide-and-conquer
- Intersection cuts for polynomial optimization
- Intersection cuts for bilevel optimization
- Hypergraph Cuts with General Splitting Functions
- scientific article; zbMATH DE number 637334
- Depth-optimized convexity cuts
- scientific article; zbMATH DE number 1182577
- Multirow Intersection Cuts Based on the Infinity Norm
- Cutting plane algorithm for convex generalized disjunctive programs
Cites work
- scientific article; zbMATH DE number 3550465 (Why is no real title available?)
- scientific article; zbMATH DE number 734930 (Why is no real title available?)
- scientific article; zbMATH DE number 1757966 (Why is no real title available?)
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Computational experiments with cross and crooked cross cuts
- Computing with multi-row gomory cuts
- Constraint Integer Programming: A New Approach to Integrate CP and MIP
- Design and verify: a new scheme for generating cutting-planes
- Disjunctive Programming
- Experiments with two-row cuts from degenerate tableaux
- Generalized intersection cuts and a new cut generating paradigm
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Lectures on Polytopes
- Lexicography and degeneracy: Can a pure cutting plane algorithm work?
- Local cuts revisited
- MIPLIB 2003
- MIR closures of polyhedral sets
- Mixed integer programming: analyzing 12 years of progress
- On t-branch split cuts for mixed-integer programs
- On optimizing over lift-and-project closures
- On the polyhedrality of cross and quadrilateral closures
- On the practical strength of two-row tableau cuts
- On the relative strength of different generalizations of split cuts
- Optimizing over the split closure
- Partial hyperplane activation for generalized intersection cuts
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- The strength of multi-row models
Cited in
(3)
This page was built for publication: Partial hyperplane activation for generalized intersection cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175444)
