Optimization Online


Partial hyperplane activation for generalized intersection cuts

Aleksandr M. Kazachkov (akazachk***at***cmu.edu)
Selvaprabu Nadarajah (selvan***at***uic.edu)
Egon Balas (eb17***at***andrew.cmu.edu)
François Margot (fmargot11***at***gmail.com)

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 identify properties related to strong cuts that can be targeted in the future.

Keywords: mixed-integer linear programming, cutting planes, intersection cuts

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report, Carnegie Mellon University, Pittsburgh, PA, March 2017

Download: [PDF]

Entry Submitted: 03/06/2017
Entry Accepted: 03/06/2017
Entry Last Modified: 12/16/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society