Abstract
We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive “perspective cuts”, a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch & Cut approaches for at least two models that, either “naturally” or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahn, S., Escudero, L.F., Guignard-Spielberg, M.: On modeling robust policies for financial trading. In: T.A. Ciriani and R.L. Leachman (eds.) Optimization in Industry 2, Wiley Chichester, 1994 pp 163–184
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Mathematical Programming 58, 295–324 (1993)
Borghetti, A., Frangioni, A., Lacalandra, F., Nucci, C.A.: Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment. IEEE Transactions on Power Systems 18 (1), 1–10 (2003)
Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Mathematical Programming 86, 595–614 (1999)
Duran, M.A., Grossmann, I.E: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming 36, 307–339 (1986)
Frangioni, A., Gentile, C.: Perspective cuts for 0–1 mixed integer programs. Technical report 577, Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti” (IASI-CNR), 2002
Frangioni, A.: Generalized bundle methods. SIAM Journal on Optimization 13 (1), 117–156 (2002)
Frangioni, A.: About lagrangian methods in integer optimization. Annals of Operations Research, To appear 2005
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms I–- fundamentals. Grundlehren Math. Wiss. 305 Springer-Verlag, New York 1993
Jobst, N.J., Horniman, M.D., Lucas, C.A., Mitra, G.: Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitative Finance 1, Wiley Chichester, 2001, pp 1–13
Kallrath, J., Wilson, J.M.: Business optimization. Macmillan Press Ltd. Houndmills, 1997
Markowitz, H.M.: Portfolio selection. Journal of Finance 7, 77–91 (1952)
Padberg, M.W., Rinaldi, G.: A branch and cut algorithm for resolution of large scale symmetric salesman problems. SIAM Review 33, 60–100 (1991)
Pardalos, P.M., Rodgers, G.P.: Computing aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45, 131–144 (1990)
Rikun, A.D.: A convex envelope formula for multilinear functions. Journal of Global Optimimization 10, 425–437 (1997)
Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0-1 mixed convex programming. Mathematical Programming 86, 515–532 (1999)
Tawarmalani, M., Sahinidis, N.V.: Convex extensions and envelopes of lower semi-continuous functions. Mathematical Programming 93, 515–532 (2002)
Zamora, J.M., Grossmann, I.E.: A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Comput & Chem. Engin. 22, 367–384 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Frangioni, A., Gentile, C. Perspective cuts for a class of convex 0–1 mixed integer programs. Math. Program. 106, 225–236 (2006). https://doi.org/10.1007/s10107-005-0594-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0594-3