When Lift-and-Project Cuts Are Different

Egon Balas and Thiago Serra
Additional contact information
Thiago Serra: Freeman College of Management, Bucknell University, Lewisburg, Pennsylvania 17837

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 822-834

Abstract: In this paper, we present a method to determine if a lift-and-project cut for a mixed-integer linear program is irregular, in which case the cut is not equivalent to any intersection cut from the bases 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 nonsplit disjunctions. Although it has been known for a while that lift-and-project cuts from split disjunctions are always equivalent to intersection cuts and consequently to such multirow cuts, it has been 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 basic 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. Second, we provide a mixed-integer formulation that checks whether there is a regular CGLP solution for a given cut that is regular in a broader sense, which also encompasses irregular cuts that are implied by the regular cut closure. Third, we describe a numerical procedure based on such formulation that identifies irregular lift-and-project cuts. Finally, we use this method to evaluate how often lift-and-project cuts from simple t -branch split disjunctions are irregular, and thus not equivalent to multirow cuts, on 74 instances of the Mixed Integer Programming Library (MIPLIB) benchmarks.

Keywords: integer programming; Gomory cuts; intersection cuts; lift-and-project cuts; multirow cuts (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0943 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:822-834

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().