Journal article
Reformulating the disjunctive cut generating linear program
Annals of operations research, Vol.295(1), pp.363-384
12/01/2020
DOI: 10.1007/s10479-020-03709-2
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 (x) over bar 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 (x) over bar 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 (x) over bar 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 (x) over bar. 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.
Details
- Title: Subtitle
- Reformulating the disjunctive cut generating linear program
- Creators
- Thiago Serra - Bucknell University
- Resource Type
- Journal article
- Publication Details
- Annals of operations research, Vol.295(1), pp.363-384
- Publisher
- Springer Nature
- DOI
- 10.1007/s10479-020-03709-2
- ISSN
- 0254-5330
- eISSN
- 1572-9338
- Number of pages
- 22
- Language
- English
- Date published
- 12/01/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984696655402771
Metrics
1 Record Views