Partial hyperplane activation for generalized intersection cuts

  • The generalized intersection cut 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Aleksandr M. Kazachkov, Selvaprabu Nadarajah, Egon Balas, François Margot
DOI:https://doi.org/10.1007/s12532-019-00166-2
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2019
Tag:Software; Theoretical Computer Science
Volume:12
Issue:1
Page Number:39
First Page:69
Last Page:107
Mathematical Programming Computation :MPC 2020 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.