×

zbMATH — the first resource for mathematics

A hybrid LP/NLP paradigm for global optimization relaxations. (English) Zbl 1400.90227
Summary: Polyhedral relaxations have been incorporated in a variety of solvers for the global optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.

MSC:
90C11 Mixed integer programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmadi, AA; Olshevsky, A; Parrilo, PA; Tsitsiklis, JN, NP-hardness of deciding convexity of quartic polynomials and related problems, Math. Program., 137, 453-476, (2013) · Zbl 1274.90516
[2] Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum Press, New York (1988) · Zbl 0679.90029
[3] Bao, X.: Automatic convexity detection for global optimization. Master’s thesis, Department of Chemical Engineering, University of Illinois at Urbana-Champaign (2007)
[4] Bao, X; Khajavirad, A; Sahinidis, NV; Tawarmalani, M, Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1-37, (2015) · Zbl 1317.90243
[5] Beale, EML; Forrest, JJH, Global optimization using special ordered sets, Math. Program., 10, 52-69, (1976) · Zbl 0331.90056
[6] Beale, EML; Tomlin, JA; Lawrence, J (ed.), Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables, 447-454, (1970), London
[7] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[8] Bertsekas, DP; Yu, H, A unifying polyhedral approximation framework for convex optimization, SIAM J. Optim., 21, 333-360, (2011) · Zbl 1218.90154
[9] Bonami, P; Biegler, LT; Conn, AR; Cornuejols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028
[10] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[11] Bussieck, MR; Drud, AS; Meeraus, A, Minlplib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[12] Chinneck, JW, Analyzing mathematical programs using mprobe, Ann. Oper. Res., 104, 33-48, (2001) · Zbl 1007.90064
[13] CMU-IBM open source MINLP project test set. http://egon.cheme.cmu.edu/ibm/page.htm
[14] COIN-OR Project. CBC 2.9.7 Coin Branch and Cut programming solver. https://projects.coin-or.org/Cbc
[15] COIN-OR Project. FilterSD 2 Coin FilterSD solver. https://projects.coin-or.org/filterSD
[16] Dolan, E; Moré, J, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[17] Domes, F; Neumaier, A, Constraint propagation on quadratic constraints, Constraints, 15, 404-429, (2010) · Zbl 1208.68200
[18] Drud, A.: CONOPT 3.17A, User’s Manual. ARKI Consulting and Development A/S, Bagsvaerd, Denmark (2016)
[19] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[20] Fourer, R; Maheshwari, C; Neumaier, A; Orban, D; Schichl, H, Convexity and concavity detection in computational graphs: tree walks for convexity assessment, INFORMS J. Comput., 22, 26-43, (2010) · Zbl 1243.90004
[21] Fourer, R; Orban, D, Drampl: a meta solver for optimization problem analysis, CMS, 7, 437-463, (2010) · Zbl 1243.90005
[22] Gamrath, G., Fischer, T., Gally, T., Gleixner, A.M., Hendel, G., Koch, Th., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, Ch., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J.T., Witzig, J.: The scip optimization suite 3.2. Technical Report 15-60, ZIB (2016)
[23] GAMS Performance tools. http://www.gamsworld.org/performance/tools.htm. Accessed 7 May 2018
[24] GAMS/EXAMINER: User’s Manual. https://www.gams.com/latest/docs/S_EXAMINER.html. Accessed 7 May 2018
[25] GAMS/SBB: User’s Manual. https://www.gams.com/latest/docs/S_SBB.html. Accessed 7 May 2018
[26] Gill, P.E., Murray, W., Saunders, M.A.: User’s Guide for SNOPT 7: A FORTRAN Package for Large-Scale Nonlinear Programming. Technical report, University of California, San Diego and Stanford University, CA (2008)
[27] GLOBAL Library. http://www.gamsworld.org/global/globallib.htm. Accessed 7 May 2018
[28] Grant,M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, (2014, March)
[29] Grant, M; Boyd, S; Ye, Y; Liberti, L (ed.); Maculan, N (ed.), Disciplined convex programming, 155-210, (2006), Boston, MA · Zbl 1130.90382
[30] IBM: CPLEX Optimizer (2016). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Accessed 7 May 2018
[31] Kearfott, RB, Globsol user guide, Optim. Methods Softw., 24, 687-708, (2009) · Zbl 1180.90314
[32] Kelley, JE, The cutting plane method for solving convex programs, J. SIAM, 8, 703-712, (1960) · Zbl 0098.12104
[33] Lin, Y; Schrage, L, The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325
[34] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[35] Misener, R; Floudas, ChA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Global Optim., 59, 503-526, (2014) · Zbl 1301.90063
[36] Monnigmann, M, Efficient calculation of bounds on spectra of Hessian matrices, SIAM J. Sci. Comput., 30, 2340-2357, (2008) · Zbl 1181.65055
[37] Murtagh, B.A., Saunders, M.A.: MINOS 5.5 User’s Guide. Technical Report SOL 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, CA (1995)
[38] Nenov, I., Fylstra, D., Kolev, L.: Convexity determination in the microsoft excel solver using automatic differentiation techniques. In: The 4th International Conference on Automatic Differentiation (2004)
[39] Neumaier, A; Shcherbina, O, Safe bounds in linear and mixed-integer linear programming, Math. Program., 99, 283-296, (2004) · Zbl 1098.90043
[40] Princeton Library. http://www.gamsworld.org/performance/princetonlib/princetonlib.htm. Accessed 7 May 2018
[41] Rosen, JB; Pardalos, PM, Global minimization of large-scale constrained concave quadratic problems by separable programming, Math. Program., 34, 163-174, (1986) · Zbl 0597.90066
[42] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Global Optim., 8, 107-139, (1996) · Zbl 0856.90103
[43] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Global Optim., 8, 201-205, (1996) · Zbl 0856.90104
[44] Sahinidis, N.V.: BARON 12.1.0: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2013)
[45] 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
[46] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[47] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[48] Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. PhD thesis, Humboldt-Universität zu, Berlin (2012)
[49] Wächter, A; Biegler, LT, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[50] Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 253-280, (2002) · Zbl 1035.90051
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.