×

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. (English) Zbl 1180.90206

Summary: Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally generated [the first author et al., Math. Program., Ser. A 58, No. 3, 295–324 (1993; Zbl 0796.90041)] by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP [the first author and M. Perregaard, Math. Program. 94, No. 2–3(B), 221–245 (2003; Zbl 1030.90068)], has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau.
In this paper; we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in [the first author and Perregaard, loc. cit.], and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.

MSC:

90C11 Mixed integer programming

Software:

COIN-OR; Cgllandp
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas E.: Disjunctive programming. Ann. Discret. Math. 5, 3–51 (1979) · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X
[2] Balas E.: Generating Deepest Mixed Integer Cuts by Disjunctive Modularization. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA (2002)
[3] Balas, E., Bonami, P.: New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing. In: Fischetti, M., Williamson, D. (eds.) Integer Programming and Combinatorial Optimization (IPCO 12), Lecture Notes in Computer Science, vol. 4513, pp. 89–104. Springer, New York (2007) · Zbl 1136.90399
[4] Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[5] Balas E., Ceria S., Cornuéjols G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 112, 1229–1246 (1996) · Zbl 0880.90105 · doi:10.1287/mnsc.42.9.1229
[6] Balas E., Ceria S., Cornuéjols G., Natraj: Gomory cuts revisited. Oper. Res. Lett. 19, 1–10 (1996) · Zbl 0865.90098 · doi:10.1016/0167-6377(96)00007-7
[7] Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0–1 programming. Math. Program. B. 94, 221–245 (2003) · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y
[8] Balas E., Saxena A.: Optimizing over the split closure. Math. Program. A. 113, 219–240 (2008) · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5
[9] COIN-OR website: http://www.coin-or.org/
[10] CglLandP: https://projects.coin-or.org/Cgl/wiki/CglLandP
[11] Dash S., Gunluk O., Lodi A.: MIR closures of polyhedral sets. Math. Program. A. 121, 33–60 (2009) · Zbl 1184.90107 · doi:10.1007/s10107-008-0225-x
[12] Fischetti, M., Lodi, A., Tramontani: On the separation of disjunctive cuts. Math. Program. A. (2009), to appear
[13] Perregaard, M.: A practical implementation of lift-and-project cuts. International Symposium on Mathematical Programming, Copenhagen (2003) · Zbl 1030.90068
[14] Perregaard, M.: Generating disjunctive cuts for mixed integer programs. Ph.D. Thesis, Carnegie Mellon University (2003) · Zbl 1030.90068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.