Abstract
Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andersen, K., Louveaux Q., Weismantel, R., Wolsey, L.: Cutting planes from two rows of a simplex Tableau. IPCO XII, pp. 1–15, Ithaca, New York (2007)
Balas E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
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)
Balas E., Bonami P.: Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Program. Comput. 1, 165–199 (2009)
Balas E., Jeroslow R.G.: Strengthening cuts for mixed-integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)
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)
Borozan V., Cornuéjols G.: Minimal valid inequalities for integer constraints. Math. Oper. Res. 34, 538–546 (2009)
Cook W.J., Kannan R., Schrijver A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)
Dey, S., Wolsey, L.: Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. IPCO XIII, pp. 263–275, Bertinoro, Italy (2008)
Fischetti, M., Lodi, A., Tramontani, A.: On the separation of disjunctive cuts. Math. Program. A (2009). doi:10.1007/s10107-009-0300-y
Gomory R., Johnson E.: Some continuous functions related to corner polyhedra. Math. Program. 3, 23–85 (1972)
Grűnbaum B.: Convex Polytopes. Interscience Publishers, NY (1967)
Johnson E.: On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)
Lovász L.: Geometry of numbers and integer programming. In: Iri, M., Tanabe, K. (eds) Mathematical Programming, pp. 177–201. KTK Scientific Publishers, Tokyo (1989)
Wesselmann F.: Strengthening Gomory Mixed-Integer Cuts: A Computational Study. University of Paderborn, Paderborn (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
E. Balas: Research supported by the National Science Foundation through grant CMMI-1024554.
E. Balas, F. Margot: Research supported by the Office of Naval Research through contract N00014-09-1-0033.
Rights and permissions
About this article
Cite this article
Balas, E., Margot, F. Generalized intersection cuts and a new cut generating paradigm. Math. Program. 137, 19–35 (2013). https://doi.org/10.1007/s10107-011-0483-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0483-x