Abstract
Disjunctive cuts for Mixed-Integer Linear Programs (MIPs) were introduced by Egon Balas in the late 1970s and have been successfully exploited in practice since the late 1990s. In this paper we investigate the main ingredients of a disjunctive cut separation procedure, and analyze their impact on the quality of the root-node bound for a set of instances taken from MIPLIB library. We compare alternative normalization conditions, and try to better understand their role. In particular, we point out that constraints that become redundant (because of the disjunction used) can produce over-weak cuts, and analyze this property with respect to the normalization used. Finally, we introduce a new normalization condition and analyze its theoretical properties and computational behavior. Along the way, we make use of a number of small numerical examples to illustrate some basic (and often misinterpreted) disjunctive programming features.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balas E.: A modified lift-and-project procedure. Math. Program. 79, 19–31 (1997)
Balas E.: Disjunctive programming. Ann. Discrete. Math. 5, 3–51 (1979)
Balas E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89, 3–44 (1998)
Balas, E., Bonami, P.: Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Technical Report, Tepper School of Business, CMU (2008)
Balas E., Ceria S., Cornuéjols G.: Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manage. Sci. 42, 1229–1246 (1996)
Balas E., Jeroslow R.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)
Balas E., Perregaard M.: Lift-and-project for mixed 0–1 programming: recent progress. Discrete Appl. Math. 123, 129–154 (2002)
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. Ser. B 94, 221–245 (2003)
Balas E., Saxena A.: Optimizing over the split closure. Math. Program. Ser. A 113, 219–240 (2008)
Beasley, J.E.: OR-Library: a collection of test data sets for a variety of Operations Research (OR) problems. http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. http://www.caam.rice.edu/~bixby/miplib/miplib.html
Bonami, P.: Étude et mise en oeuvre d’approches polyédriques pour la résolution de programmes en nombres entiers ou mixtes généraux, PhD Thesis, Université de Paris 6 (2003)
Ceria S., Soares J.: Disjunctive cuts for mixed 0–1 programming: duality and lifting. Columbia University, GSB (1997)
Chvátal V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305–337 (1973)
Cook W.J., Kannan R., Schrijver A.: Chvátal closures for mixed integer programming problems. Math. Program. Ser. A 47, 155–174 (1990)
Christof, T., Löbel, A.: PORTA—POlyhedron Representation Transformation Algorithm. http://www.zib.de/Optimization/Software/Porta/
Dash S., Günlük O., Lodi A.: On the MIR closure of polyhedra. In: Fischetti, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization—IPCO 2007. Lecture Notes in Computer Science, vol. 4513, pp. 337–351. Springer, Berlin (2007)
Fischetti M., Lodi A.: Optimizing over the first Chvátal closure. Math. Program. Ser. B 110, 3–20 (2007)
Gomory, R.E.: An algorithm for the mixed integer problem, RM-2597, The RAND Corporation (1960)
Author information
Authors and Affiliations
Corresponding author
Additional information
Matteo Fischetti was supported in part by the EU project ARRIVAL (contract n. FP6-021235-2) and by MiUR, Italy (PRIN 2006 project “Models and algorithms for robust network optimization”).
Andrea Lodi was supported in part by the EU project ARRIVAL (contract n. FP6-021235-2).
Rights and permissions
About this article
Cite this article
Fischetti, M., Lodi, A. & Tramontani, A. On the separation of disjunctive cuts. Math. Program. 128, 205–230 (2011). https://doi.org/10.1007/s10107-009-0300-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0300-y