Optimization Online


When Lift-and-Project Cuts are Different

Egon Balas (eb17***at***andrew.cmu.edu)
Thiago Serra (tserra***at***gmail.com)

Abstract: In this paper, we present a method to determine if a lift-and-project cut for a mixed-integer linear program is regular, in which case the cut is equivalent to an intersection cut from some basis of the linear relaxation. This is an important question due to the intense research activity for the past decade on cuts from multiple rows of simplex tableau as well as on lift-and-project cuts from non-split disjunctions. While it is known since Balas and Perregaard (2003) that such equivalence always holds for lift-and-project cuts from split disjunctions, Balas and Kis (2016) have recently shown that there is a necessary and sufficient condition in the case of arbitrary disjunctions: a lift-and-project cut is regular if, and only if, it corresponds to a regular solution of the Cut Generating Linear Program (CGLP). This paper has four contributions. First, we state a result that simplifies the verification of regularity for basic CGLP solutions from Balas and Kis (2016). Second, we provide a mixed-integer formulation that checks whether there is a regular CGLP solution for a given cut. Third, we describe a numerical procedure that verifies if a lift-and-project cut is not regular. Finally, we use this method to evaluate how often lift-and-project cuts are irregular, and thus not equivalent to multi-row cuts, on 74 instances of the MIPLIB benchmarks.

Keywords: integer programming; Gomory cuts; intersection cuts; lift-and-project cuts; multi-row cuts

Category 1: Integer Programming (Cutting Plane Approaches )

Citation: INFORMS Journal on Computing (to appear)

Download: [PDF]

Entry Submitted: 09/17/2018
Entry Accepted: 09/17/2018
Entry Last Modified: 01/24/2020

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