Abstract
We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cuts. We apply the above development to the case where P is (the closed convex hull of) a union, and more particularly a union of polyhedra (case of disjunctive cuts). We conclude with some considerations on the design of efficient cut generators. The paper also contains an appendix, reviewing some fundamental concepts of convex analysis.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3–51 (1979)
Balas, E., Cornuéjols, G., Ceria, S.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Prog. 58, 295–324 (1993)
Balas, E., Perregaard, M.: Lift-and-project for mixed 0-1 programming: recent progress. Discrete Appl. Math. 123, 129–154 (2002)
Bonami, P.: Etude et mise en œuvre 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
Bonami, P.: Personal communication, 2004
Ceria, S., Soares, J.: Disjunctive cuts for mixed 0-1 programming: duality and lifting. Technical report, GSB, Columbia Univ., 1997
Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Prog. 86 (3), 595–614 (1999)
Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programs. Math. Prog. 47, 155–174 (1990)
Gomory, R.: An algorithm for the mixed integer problem. Technical Report RM–2597, The Rand Coporation, 1960
Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of convex analysis. Springer Verlag, Heidelberg, 2001
Rey, P.A.: Análise convexa e métodos Lift-and-Project para programação inteira. PhD thesis, Dept. of Electrical Engineering, PUC, Rio, Brazil, 2001
Rockafellar, R.T.: Convex analysis. Princeton University Press, 1970
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF grant DMII-0352885, ONR grant N00014-03-1-0188, INRIA grant ODW and IBM.
Rights and permissions
About this article
Cite this article
Cornuéjols, G., Lemaréchal, C. A convex-analysis perspective on disjunctive cuts. Math. Program. 106, 567–586 (2006). https://doi.org/10.1007/s10107-005-0670-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0670-8