Partial hyperplane activation for generalized intersection cuts
From MaRDI portal
Publication:2175444
DOI10.1007/S12532-019-00166-2zbMATH Open1437.90111arXiv1703.02221OpenAlexW2967078236WikidataQ127390538 ScholiaQ127390538MaRDI QIDQ2175444FDOQ2175444
Authors: Aleksandr M. Kazachkov, Selvaprabu Nadarajah, E. Balas, François Margot 
Publication date: 29 April 2020
Published in: Mathematical Programming Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1703.02221
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
- MIPLIB 2003
- Lectures on Polytopes
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Some polyhedra related to combinatorial problems
- Mixed integer programming: analyzing 12 years of progress
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Disjunctive Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- On optimizing over lift-and-project closures
- Optimizing over the split closure
- On \(t\)-branch split cuts for mixed-integer programs
- Constraint Integer Programming: A New Approach to Integrate CP and MIP
- Generalized intersection cuts and a new cut generating paradigm
- On the polyhedrality of cross and quadrilateral closures
- MIR closures of polyhedral sets
- Local cuts revisited
- Title not available (Why is that?)
- Lexicography and degeneracy: Can a pure cutting plane algorithm work?
- Experiments with two-row cuts from degenerate tableaux
- On the practical strength of two-row tableau cuts
- On the relative strength of different generalizations of split cuts
- The strength of multi-row models
- Computational experiments with cross and crooked cross cuts
- Computing with multi-row gomory cuts
- Design and verify: a new scheme for generating cutting-planes
- Partial hyperplane activation for generalized intersection cuts
Cited In (3)
Uses Software
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)
