×

Solving mixed-integer nonlinear optimization problems using simultaneous convexification: a case study for gas networks. (English) Zbl 1473.90093

Summary: Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint function at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method that relies on determining the convex envelope of linear combinations of the constraint functions and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming

Software:

ANTIGONE; SCIP; GasLib; MINLP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstreicher, KM; Burer, S., Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124, 1, 33-43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9
[2] Ballerstein, M.: Convex Relaxations for Mixed-Integer Nonlinear Programs. Ph.D. thesis, Eidgenössische Technische Hochschule Zürich (2013) · Zbl 1381.90002
[3] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numerica, 22, 1-131 (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032
[4] Boukouvala, F.; Misener, R.; Floudas, CA, Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization CDFO, Eur. J. Oper. Res., 252, 3, 701-727 (2016) · Zbl 1346.90677 · doi:10.1016/j.ejor.2015.12.018
[5] Bussieck, M.R., Vigerske, S.: MINLP Solver Software (2014)
[6] Eronen, VP; Mäkelä, MM; Westerlund, T., On the generalization of ecp and oa methods to nonsmooth convex minlp problems, Optimization, 63, 7, 1057-1073 (2014) · Zbl 1295.90022 · doi:10.1080/02331934.2012.712118
[7] Geißler, B.: Towards globally optimal solutions for minlps by discretization techniques with applications in gas network optimization. Ph.D. thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (2011)
[8] Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 5.0. Technical Report, pp. 17-61, Zuse Institute Berlin (2017)
[9] Grossmann, IE; Caballero, JA; Yeomans, H., Mathematical Programming Approaches to the Synthesis of Chemical Process Systems, Korean J. Chem. Eng., 16, 4, 407-426 (1999) · doi:10.1007/BF02698263
[10] Jach, M.; Michaels, D.; Weismantel, R., The Convex Envelope of \((n-1)\)-Convex Functions, SIAM J. Optim., 19, 3, 1451-1466 (2008) · Zbl 1176.90467 · doi:10.1137/07069359X
[11] Kelley, JE Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053
[12] Khajavirad, A.; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Math. Program., 137, 1, 371-408 (2013) · Zbl 1284.90055 · doi:10.1007/s10107-011-0496-5
[13] Koch, T., Hiller, B., Pfetsch, M., Schewe, L. (eds.): Evaluating gas network capacities. MOS-SIAM Ser. Optim. (2015). doi:10.1137/1.9781611973693 · Zbl 1322.90007
[14] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[15] Liberti, L.; Pantelides, CC, Convex envelopes of monomials of odd degree, J. Global Optim., 25, 2, 157-168 (2003) · Zbl 1030.90117 · doi:10.1023/A:1021924706467
[16] Locatelli, M.; Schoen, F., Global optimization: theory, algorithms, and applications, Soc. Ind. Appl. Math. (2013) · Zbl 1286.90003 · doi:10.1137/1.9781611972672
[17] Locatelli, M.; Schoen, F., On convex envelopes for bivariate functions over polytopes, Math. Program., 144, 1, 65-91 (2014) · Zbl 1295.90055 · doi:10.1007/s10107-012-0616-x
[18] Martin, A.; Möller, M.; Moritz, S., Mixed integer models for the stationary case of gas network optimization, Math. Program., 105, 2, 563-582 (2006) · Zbl 1085.90035 · doi:10.1007/s10107-005-0665-5
[19] Merkert, M.: Solving mixed-integer linear and nonlinear network optimization problems by local reformulations and relaxations. Ph.D. thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (2017)
[20] Mertens, N.: Relaxation Refinement for Mixed Integer Nonlinear Programs with Applications in Engineering. Ph.D. thesis, Technische Universität Dortmund (2019)
[21] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 2, 207-224 (2005) · Zbl 1099.90045 · doi:10.1007/s10107-005-0580-9
[22] Misener, R.; Floudas, CA, ANTIGONE: Algorithms for coNTinuous integer global optimization of nonlinear equations, J. Global Optim. (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2
[23] Rikun, AD, A convex envelope formula for multilinear functions, J. Global Optim., 10, 4, 425-437 (1997) · Zbl 0881.90099 · doi:10.1023/A:1008217604285
[24] Ruiz, JP; Grossmann, IE, Using redundancy to strengthen the relaxation for the global optimization of minlp problems, Comput. Chem. Eng., 35, 12, 2729-2740 (2011) · doi:10.1016/j.compchemeng.2011.01.035
[25] Schmidt, M.; Aßmann, D.; Burlacu, R.; Humpola, J.; Joormann, I.; Kanelakis, N.; Koch, T.; Oucherif, D.; Pfetsch, ME; Schewe, L.; Schwarz, R.; Sirvent, M., GasLib-a library of gas network instances, Data, 2, 4, 40 (2017) · doi:10.3390/data2040040
[26] Sherali, HD; Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, J. Global Optim., 2, 4, 379-410 (1992) · Zbl 0791.90056 · doi:10.1007/BF00122429
[27] Tawarmalani, M., Inclusion certificates and simultaneous convexification of functions, Math. Program., 5, 94 (2010)
[28] Tawarmalani, M.; Sahinidis, NV, Semidefinite relaxations of fractional programs via novel convexification techniques, J. Global Optim., 20, 2, 133-154 (2001) · Zbl 1001.90064 · doi:10.1023/A:1011233805045
[29] Tawarmalani, M.; Sahinidis, NV, Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 2, 247-263 (2002) · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z
[30] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
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.