×

zbMATH — the first resource for mathematics

A decomposition method for MINLPs with Lipschitz continuous nonlinearities. (English) Zbl 1426.90053
Summary: Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for many problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods.

MSC:
90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C30 Nonlinear programming
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ainsworth, M., Oden, J.T.: A Posteriori Error Estimation in Finite Element Analysis. Pure and Applied Mathematics. Wiley, New York (2000). https://doi.org/10.1002/9781118032824 · Zbl 1008.65076
[2] Al-Khayyal, FA; Sherali, HD, On finitely terminating branch-and-bound algorithms for some global optimization problems, SIAM J. Optim., 10, 1049-1057, (2000) · Zbl 0994.65068
[3] Babuška, I., Strouboulis, T.: The Finite Element Method and Its Reliability. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2001) · Zbl 0995.65501
[4] Baes, M.; Pia, A.; Nesterov, Y.; Onn, S.; Weismantel, R., Minimizing lipschitz-continuous strongly convex functions over integer points in polytopes, Math. Progr., 134, 305-322, (2012) · Zbl 1262.90128
[5] Becker, R.; Rannacher, R.; Iserles, A. (ed.), An optimal control approach to a posteriori error estimation, 1-102, (2001), Cambridge · Zbl 1105.65349
[6] Belotti, P.: COUENNE: A User’s Manual. https://projects.coin-or.org/Couenne. Accessed 12 Feb 2018
[7] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172
[8] Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252, (1962) · Zbl 0109.38302
[9] Bonami, P.; Biegler, LT; Conn, AR; Cornuéjols, 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., 15, 186-204, (2008) · Zbl 1151.90028
[10] Borchers, B.; Mitchell, JE, An improved branch and bound algorithm for mixed integer nonlinear programs, Comput. Oper. Res., 21, 359-367, (1994) · Zbl 0797.90069
[11] Burlacu, R., Geissler, B., Schewe, L.: Solving mixed-integer nonlinear programs using adaptively refined mixed-integer linear programs. Technical Report., Friedrich-Alexander Universität Erlangen-Nürnberg (2017). https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/151
[12] Colebrook, CF, Turbulent flow in pipes with particular reference to the transition region between smooth and rough pipe laws, J. Inst. Civ. Eng., 11, 133-156, (1939)
[13] DESFA. http://www.desfa.gr (2016)
[14] Dempe, S.: Foundations of Bi-level Programming. Springer, Berlin (2002). https://doi.org/10.1007/b101970 · Zbl 1038.90097
[15] Dempe, S.: Foundations of Bi-level Programming. Springer, Berlin (2002). https://doi.org/10.1007/b101970 · Zbl 1038.90097
[16] Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., Kalashnykova, N.: Bilevel Programming Problems. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-45827-3 · Zbl 1338.90005
[17] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Progr., 36, 307-339, (1986) · Zbl 0619.90052
[18] Eriksson, K.; Estep, D.; Hansbo, P.; Johnson, C.; Iserles, A. (ed.), Introduction to adaptive methods for differential equations, 105-158, (1995), Cambridge · Zbl 0829.65122
[19] Evtuschenko, YG, Numerical methods for finding global extrema, USSR Comput. Math. Math. Phys., 11, 38-54, (1971) · Zbl 0258.90045
[20] Feistauer, M.M.: Mathematical Methods in Fluid Dynamics. Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, New York (1993)
[21] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Progr., 66, 327-349, (1994) · Zbl 0833.90088
[22] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., San Francisco (1979) · Zbl 0411.68039
[23] Gauvin, J.; Dubeau, F.; Guignard, M. (ed.), Differential properties of the marginal function in mathematical programming, 101-119, (1982), Berlin · Zbl 0502.90072
[24] Geissler, 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)
[25] Geißler, Björn; Martin, Alexander; Morsi, Antonio; Schewe, Lars, Using Piecewise Linear Functions for Solving MINLPs, 287-314, (2011), New York, NY · Zbl 1242.90132
[26] Geißler, Björn; Martin, Alexander; Morsi, Antonio; Schewe, Lars, Chapter 6: The MILP-relaxation approach, 103-122, (2015), Philadelphia, PA · Zbl 1343.90009
[27] Geissler, B.; Morsi, A.; Schewe, L.; Jünger, M. (ed.); Reinelt, G. (ed.), A new algorithm for MINLP applied to gas transport energy cost minimization, 321-353, (2013), Berlin · Zbl 1317.90209
[28] Geissler, B.; Morsi, A.; Schewe, L.; Schmidt, M., Solving power-constrained gas transportation problems using an MIP-based alternating direction method, Comput. Chem. Eng., 82, 303-317, (2015)
[29] Geißler, Björn; Morsi, Antonio; Schewe, Lars; Schmidt, Martin, Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods, INFORMS Journal on Computing, 30, 309-323, (2018)
[30] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024
[31] 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 17-61, ZIB, Takustr.7, 14195 Berlin (2017)
[32] Göttlich, S.; Potschka, A.; Ziegler, U., Partial outer convexification for traffic light optimization in road networks, SIAM J. Sci. Comput., 39, b53-b75, (2017) · Zbl 1381.90028
[33] Grimm, V.; Schewe, L.; Schmidt, M.; Zöttl, G., Uniqueness of market equilibrium on a network: a peak-load pricing approach, Eur. J. Oper. Res., 261, 971-983, (2017) · Zbl 1403.91148
[34] Gu, Z., Rothberg, E., Bixby, R.: Gurobi Optimizer Reference Manual, Version 6.5.0 (2015)
[35] Gugat, M.; Hante, FM; Hirsch-Dick, M.; Leugering, G., Stationary states in gas networks, Netw. Heterog. Media, 10, 295-320, (2015) · Zbl 1332.93154
[36] Gugat, Martin; Leugering, Günter; Martin, Alexander; Schmidt, Martin; Sirvent, Mathias; Wintergerst, David, Towards simulation based mixed-integer optimization with differential equations, Networks, 72, 60-83, (2018) · Zbl 1397.90308
[37] Gugat, Martin; Schultz, Rüdiger; Wintergerst, David, Networks of pipelines for gas with nonconstant compressibility factor: stationary states, Computational and Applied Mathematics, 37, 1066-1097, (2016) · Zbl 1416.76253
[38] Hansen, P.; Jaumard, B.; Horst, R. (ed.); Pardalos, PM (ed.), Lipschitz optimization, 407-493, (1995), New York · Zbl 0833.90105
[39] Hante, FM, Relaxation methods for hyperbolic pde mixed-integer optimal control problems, Optim. Control Appl. Methods, 38, 1103-1110, (2017) · Zbl 1386.49047
[40] Hante, FM; Sager, S., Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl., 55, 197-225, (2013) · Zbl 1272.49026
[41] Horst, R., Deterministic global optimization with partition sets whose feasibility is not known: application to concave minimization, reverse convex constraints, dc-programming, and lipschitzian optimization, J. Optim. Theory Appl., 58, 11-37, (1988) · Zbl 0621.90064
[42] Horst, R.; Thoai, NV, Branch-and-bound methods for solving systems of lipschitzian equations and inequalities, J. Optim. Theory Appl., 58, 139-145, (1988) · Zbl 0621.90073
[43] Horst, R.; Tuy, H., On the convergence of global methods in multiextremal optimization, J. Optim. Theory Appl., 54, 253-271, (1987) · Zbl 0595.90079
[44] Horst, R., Tuy, H.: Global Optimization, 2nd edn. Springer, Berlin (1996). https://doi.org/10.1007/978-3-662-03199-5 · Zbl 0867.90105
[45] Kannan, R.; Monma, CL; Henn, R. (ed.); Korte, B. (ed.); Oettli, W. (ed.), On the computational complexity of integer programming problems, 161-172, (1977), Berlin
[46] Klatte, D.; Kummer, B.; Demyanov, VF (ed.); Pallaschke, D. (ed.), Stability properties of infima and optimal solutions of parametric optimization problems, 215-229, (1985), Berlin
[47] Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L.: Evaluating Gas Network Capacities. SIAM-MOS Series on Optimization. SIAM, Bangkok (2015). https://doi.org/10.1137/1.9781611973693 · Zbl 1322.90007
[48] Králik, J., Stiegler, P., Vostrý, Z., Záworka, J.: Dynamic Modeling of Large-Scale Networks with Application to Gas Distribution, Studies in Automation and Control, vol. 6. Elsevier, Amsterdam (1988)
[49] Kvasov, DE; Sergeyev, YD, Lipschitz global optimization methods in control problems, Autom. Remote Control, 74, 1435-1448, (2013) · Zbl 1282.90138
[50] LaMaTTO++: A Framework for Modeling and Solving Mixed-Integer Nonlinear Programming Problems on Networks. http://www.mso.math.fau.de/edom/projects/lamatto.html (2017)
[51] Labbé, M.; Violin, A., Bilevel programming and price setting problems, 4OR, 11, 1-30, (2013) · Zbl 1259.90112
[52] Leyffer, S.: Deterministic methods for mixed integer nonlinear programming. Ph.D. Thesis, University of Dundee, Dundee, Scotland, UK (1993)
[53] Li, M.; Vicente, LN, Inexact solution of NLP subproblems in MINLP, J. Glob. Optim., 55, 877-899, (2013) · Zbl 1288.90053
[54] Lindo Systems Inc. https://www.lindo.com. Accessed on 12 Feb 2018
[55] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part i—convex underestimating problems, Math. Progr., 10, 147-175, (1976) · Zbl 0349.90100
[56] Misener, R.; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[57] Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Effciency in Optimization. Wiley, New York (1983)
[58] Pfetsch, ME; Fügenschuh, A.; Geissler, B.; Geissler, N.; Gollmer, R.; Hiller, B.; Humpola, J.; Koch, T.; Lehmann, T.; Martin, A.; Morsi, A.; Rövekamp, J.; Schewe, L.; Schmidt, M.; Schultz, R.; Schwarz, R.; Schweiger, J.; Stangl, C.; Steinbach, MC; Vigerske, S.; Willert, BM, Validation of nominations in gas network optimization: models, methods, and solutions, Optim. Methods Softw., 30, 15-53, (2015) · Zbl 1325.90019
[59] Pintér, J., Extended univariate algorithms for n-dimensional global optimization, Computing, 36, 91-103, (1986) · Zbl 0572.65047
[60] Pintér, J., Global optimization on convex sets, Oper. Res. Spektrum, 8, 197-202, (1986) · Zbl 0618.90085
[61] Pintér, J., Globally convergent methods for n-dimensional multiextremal optimization, Optimization, 17, 187-202, (1986) · Zbl 0595.90071
[62] Pintér, J., Branch- and bound algorithms for solving global optimization problems with lipschitzian structure, Optimization, 19, 101-110, (1988) · Zbl 0645.90065
[63] Pintér, J., Nonlinear optimization with gams/lgo, J. Glob. Optim., 38, 79-101, (2007) · Zbl 1179.90311
[64] Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Springer, Berlin (1996). https://doi.org/10.1007/978-1-4757-2502-5 · Zbl 0842.90110
[65] Piyavskii, SA, An algorithm for finding the absolute extremum of a function, USSR Comput. Math. Math. Phys., 12, 57-67, (1972) · Zbl 0282.65052
[66] Rannacher, Rolf; Vexler, Boris; Wollner, Winnifried, A Posteriori Error Estimation in PDE-constrained Optimization with Pointwise Inequality Constraints, 349-373, (2011), Basel · Zbl 1356.49052
[67] Ríos-Mercado, RZ; Borraz-Sánchez, C., Optimization problems in natural gas transportation systems: a state-of-the-art review, Appl. Energy, 147, 536-555, (2015)
[68] Sager, S.; Jung, M.; Kirches, C., Combinatorial integral approximation, Math. Methods Oper. Res., 73, 363-380, (2011) · Zbl 1220.90073
[69] Saleh, J.: Fluid Flow Handbook. McGraw-Hill Handbooks. McGraw-Hill, New York (2002)
[70] Schmidt, M.; Assmann, 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, 40, (2017)
[71] Schmidt, M.; Steinbach, MC; Willert, BM, High detail stationary optimization models for gas networks, Optim. Eng., 16, 131-164, (2015) · Zbl 1364.90066
[72] Schmidt, Martin; Steinbach, Marc C.; Willert, Bernhard M., Chapter 10: The precise NLP model, 181-210, (2015), Philadelphia, PA · Zbl 1343.90016
[73] Schmidt, M.; Steinbach, MC; Willert, BM, High detail stationary optimization models for gas networks: validation and results, Optim. Eng., 17, 437-472, (2016) · Zbl 1364.90067
[74] Smith, EMB; Pantelides, CC, Global optimisation of nonconvex MINLPs, Comput. Chem. Eng., 21, s791-s796, (1997)
[75] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, vol. 65. Springer, Berlin (2002). https://doi.org/10.1007/978-1-4757-3532-1 · Zbl 1031.90022
[76] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Progr., 99, 563-591, (2004) · Zbl 1062.90041
[77] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Progr., 103, 225-249, (2005) · Zbl 1099.90047
[78] Tuy, H.; Horst, R., Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems, Math. Progr., 41, 161-183, (1988) · Zbl 0651.90063
[79] Vavasis, S.A.: Nonlinear Optimization: Complexity Issues. Oxford University Press Inc, Oxford (1991) · Zbl 0785.90091
[80] Verfürth, R.: A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques. Wiley, New York (1996) · Zbl 0853.65108
[81] Verfürth, R.: A Posteriori Error Estimation Techniques for Finite Element Methods. Oxford University Press, Oxford (2013). https://doi.org/10.1093/acprof:oso/9780199679423.001.0001 · Zbl 1279.65127
[82] Westerlund, T., Lundqvist, K.: Alpha-ECP, version 5.01: an interactive MINLP-solver based on the extended cutting plane method. Technical Report 01-178-A (2001)
[83] Westerlund, T.; Pettersson, F., An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136, (1995)
[84] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Progr., 106, 25-57, (2006) · Zbl 1134.90542
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.