×

A polyhedral branch-and-cut approach to global optimization. (English) Zbl 1099.90047

Summary: A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software.
In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited.
Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.

MSC:

90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

BARON; MINLP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audet, C., Hansen, P., Jaumard, B., Savard, G. : A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Prog. 87, 131–152 (2000) · Zbl 0966.90057
[2] Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum Press, 1988
[3] Böröczky K.Jr., Reitzner,M.: Approximation of smooth convex bodies by random circumscribed polytopes. Annals of Applied Probability 14, 239–273 (2004) · Zbl 1049.60009 · doi:10.1214/aoap/1075828053
[4] Bussieck, M.R.: MINLP World. http://www.gamsworld.org/minlp/index.htm 2002
[5] Chinneck, J.W.: Discovering the characteristics of mathematical programming via sampling. Optimization Methods and Software 17, 319–352 (2002) · Zbl 1038.90074 · doi:10.1080/1055678021000012480
[6] Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Prog. 36, 307–339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[7] Fourer, R., Moré, J., Munson, T., Sarich, J.: Next-generation servers for optimization as an internet resource. Available at http://iems.nwu.edu/\(\sim\)4er 2004
[8] Griewank, A.: Evaluating derivatives. Principles and Techniques of Algorithmic Differentiation, vol 19 of Frontiers in Applied Mathematics. SIAM, Philadelphia, PA, 2000 · Zbl 0958.65028
[9] Griffith, R.E., Stewart, R.A.: A nonlinear programming technique for the optimization of continuous processing systems. Management Science 7, 379–392 (1961) · Zbl 0995.90610 · doi:10.1287/mnsc.7.4.379
[10] Gruber, P.M.: Asymptotic estimates for best and stepwise approximation of convex bodies II. Forum Mathematicum 5, 521–538 (1993) · Zbl 0788.41020 · doi:10.1515/form.1993.5.521
[11] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer-Verlag, Berlin, 1993
[12] Kelley, J.E.: The cutting plane method for solving convex programs. Journal of the SIAM 8, 703–712 (1960) · Zbl 0098.12104
[13] Maheshwari, C., Neumaier, A., Schichl, H.: Convexity and concavity detection. Available at http://www.mat.univie.ac.at/\(\sim\)herman/techreports/D12convconc.ps 2003 · Zbl 1243.90004
[14] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math. Prog. 10, 147–175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[15] Meeraus, A.: GLOBAL World. http://www.gamsworld.org/global/index.htm 2002
[16] Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Habilitation thesis Humboldt-Universität zu Berlin, Germany, 2004
[17] Rote, G.: The convergence rate of the sandwich algorithm for approximating convex functions. Computing 48, 337–361 (1992) · Zbl 0787.65006 · doi:10.1007/BF02238642
[18] Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions. Journal of Global Optimization 20, 137–158 (2001) · Zbl 1001.90064 · doi:10.1023/A:1011233805045
[19] Tawarmalani, M., Sahinidis, N.V.: Convex extensions and convex envelopes of l.s.c. functions. Mathematical Programming 93, 247–263 (2002) · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z
[20] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht, 2002 · Zbl 1031.90022
[21] Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Prog. 99, 563–591 (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[22] Vandenbussche, D.: Polyhedral Approaches to Solving Nonconvex Quadratic Programs. PhD thesis, Georgia Institute of Technology, Department of Indystrial and Systems Engineering, Atlanta, GA, 2003
[23] Zamora, J.M., Grossmann, I.E.: A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Computers & Chemical Engineering 22, 367–384 (1998) · doi:10.1016/S0098-1354(96)00346-8
[24] Zamora, J.M., Grossmann, I.E.: A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. Journal of Global Optimization 14, 217–249 (1999) · Zbl 0949.90097 · doi:10.1023/A:1008312714792
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.