Reformulating the disjunctive cut generating linear program

Thiago Serra ()
Additional contact information
Thiago Serra: Bucknell University

Annals of Operations Research, 2020, vol. 295, issue 1, No 16, 363-384

Abstract: Abstract Lift-and-project cuts can be obtained by defining an elegant optimization problem over the space of valid inequalities, the cut generating linear program (CGLP). A CGLP has two main ingredients: (i) an objective function, which invariably maximizes the violation with respect to a fractional solution $${\bar{x}}$$ x ¯ to be separated; and (ii) a normalization constraint, which limits the scale in which cuts are represented. One would expect that CGLP optima entail the best cuts, but the normalization may distort how cuts are compared, and the cutting plane may not be a supporting hyperplane with respect to the closure of valid inequalities from the CGLP. This work proposes the reverse polar CGLP (RP-CGLP), which switches the roles conventionally played by objective and normalization: violation with respect to $${\bar{x}}$$ x ¯ is fixed to a positive constant, whereas we minimize the slack for a point p that cannot be separated by the valid inequalities. Cuts from RP-CGLP optima define supporting hyperplanes of the immediate closure. When that closure is full-dimensional, the face defined by the cut lays on facets first intersected by a ray from $${\bar{x}}$$ x ¯ to p, all of which corresponding to cutting planes from RP-CGLP optima if p is an interior point. In fact, these are the cuts minimizing a ratio between the slack for p and the violation for $${\bar{x}}$$ x ¯ . We show how to derive such cuts directly from the simplex tableau in the case of split disjunctions and report experiments on adapting the CglLandP cut generator library for the RP-CGLP formulation.

Keywords: Cutting planes; Lift-and-project; Integer programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-020-03709-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03709-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-020-03709-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().