{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T18:27:25Z","timestamp":1779906445567,"version":"3.53.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Research Campus MODAL","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}]},{"name":"Research Campus MODAL","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the<jats:italic>expansion planning problem<\/jats:italic>. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improves the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%.<\/jats:p>","DOI":"10.1007\/s10957-022-02029-8","type":"journal-article","created":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T15:02:48Z","timestamp":1650639768000},"page":"325-352","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Convex Relaxations for the Expansion Planning Problem"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6949-3737","authenticated-orcid":false,"given":"Ralf","family":"Lenz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7892-3951","authenticated-orcid":false,"given":"Felipe","family":"Serrano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"key":"2029_CR1","unstructured":"Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universit\u00e4t Berlin (2007)"},{"issue":"2","key":"2029_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1287\/moor.8.2.273","volume":"8","author":"FA Al-Khayyal","year":"1983","unstructured":"Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273\u2013286 (1983)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"2029_CR3","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1029\/WR013i006p00885","volume":"13","author":"E Alperovits","year":"1977","unstructured":"Alperovits, E., Shamir, U.: Design of optimal water distribution systems. Water Resour. Res. 13(6), 885\u2013900 (1977). https:\/\/doi.org\/10.1029\/WR013i006p00885","journal-title":"Water Resour. Res."},{"issue":"3","key":"2029_CR4","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1016\/j.ejor.2007.12.045","volume":"197","author":"J Andr\u00e9","year":"2009","unstructured":"Andr\u00e9, J., Bonnans, F., Cornibert, L.: Optimization of capacity expansion planning for gas transportation networks. Eur. J. Oper. Res. 197(3), 1019\u20131027 (2009). https:\/\/doi.org\/10.1016\/j.ejor.2007.12.045","journal-title":"Eur. J. Oper. Res."},{"key":"2029_CR5","unstructured":"Ballerstein, M., Michaels, D., Vigerske, S.: Linear underestimators for bivariate functions with a fixed convexity behavior. Tech. Rep. 13-02, ZIB, Takustr. 7, 14195 Berlin (2013). https:\/\/nbn-resolving.de\/urn:nbn:de:0297-zib-17641"},{"issue":"4","key":"2029_CR6","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/ijoc.2016.0697","volume":"28","author":"C Borraz-S\u00e1nchez","year":"2016","unstructured":"Borraz-S\u00e1nchez, C., Bent, R., Backhaus, S., Hijazi, H., Hentenryck, P.V.: Convex relaxations for gas expansion planning. INFORMS J. Comput. 28(4), 645\u2013656 (2016). https:\/\/doi.org\/10.1287\/ijoc.2016.0697","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"2029_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s11081-011-9141-7","volume":"13","author":"C Bragalli","year":"2012","unstructured":"Bragalli, C., D\u2019Ambrosio, C., Lee, J., Lodi, A., Toth, P.: On the optimal design of water distribution networks: a practical MINLP approach. Optim. Eng. 13(2), 219\u2013246 (2012). https:\/\/doi.org\/10.1007\/s11081-011-9141-7","journal-title":"Optim. Eng."},{"key":"2029_CR8","unstructured":"Cplex, IBM ILOG: CPLEX: High-performance software for mathematical programming and optimization. https:\/\/www.ibm.com\/analytics\/cplex-optimizer (2019). Accessed December 2019"},{"issue":"4","key":"2029_CR9","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1029\/WR026i004p00539","volume":"26","author":"O Fujiwara","year":"1990","unstructured":"Fujiwara, O., Khang, D.B.: A two-phase decomposition method for optimal design of looped water distribution networks. Water Resour. Res. 26(4), 539\u2013549 (1990). https:\/\/doi.org\/10.1029\/WR026i004p00539","journal-title":"Water Resour. Res."},{"key":"2029_CR10","unstructured":"Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., L\u00fcbbecke, M.E., Maher, S.J., Miltenberger, M., M\u00fcller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schl\u00f6sser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 6.0. ZIB-Report 18-26, Zuse Institute Berlin (2018). https:\/\/nbn-resolving.de\/urn:nbn:de:0297-zib-69361"},{"key":"2029_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-38171-3_26","volume-title":"International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"AM Gleixner","year":"2013","unstructured":"Gleixner, A.M., Weltge, S.: Learning and propagating Lagrangian variable bounds for mixed-integer nonlinear programming. In: Gomes, C., Sellmann, M. (eds.) International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 7874, pp. 355\u2013361. Springer, Berlin (2013)"},{"key":"2029_CR12","first-page":"73","volume-title":"Large-scale Optimization with Applications, The IMA Volumes in Mathematics and its Applications","author":"IE Grossmann","year":"1997","unstructured":"Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Biegler, L., Coleman, T., Conn, A., Santosa, F. (eds.) Large-scale Optimization with Applications, The IMA Volumes in Mathematics and its Applications, vol. 93, pp. 73\u2013100. Springer, New York (1997)"},{"key":"2029_CR13","doi-asserted-by":"crossref","unstructured":"Hijazi, H.: Perspective envelopes for bilinear functions. In: AIP Conference Proceedings, vol. 2070. AIP Publishing (2019)","DOI":"10.1063\/1.5089984"},{"key":"2029_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02598-7","volume-title":"Global Optimization: Deterministic Approaches","author":"R Horst","year":"1990","unstructured":"Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (1990)"},{"key":"2029_CR15","doi-asserted-by":"publisher","unstructured":"Humpola, J.: Gas network optimization by MINLP. Ph.D. thesis, Technische Universit\u00e4t Berlin (2014). https:\/\/doi.org\/10.14279\/depositonce-4255","DOI":"10.14279\/depositonce-4255"},{"issue":"3","key":"2029_CR16","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1137\/07069359X","volume":"19","author":"M Jach","year":"2008","unstructured":"Jach, M., Michaels, D., Weismantel, R.: The convex envelope of $$(n-1)$$-convex functions. SIAM J. Optim. 19(3), 1451\u20131466 (2008)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2029_CR17","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1061\/JYCEAJ.0001809","volume":"94","author":"SL Jacoby","year":"1968","unstructured":"Jacoby, S.L.: Design of optimal hydraulic networks. J. Hydraul. Div. 94(3), 641\u2013662 (1968)","journal-title":"J. Hydraul. Div."},{"issue":"1","key":"2029_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1061\/JPLEAZ.0000116","volume":"94","author":"D Karmeli","year":"1968","unstructured":"Karmeli, D., Gadish, Y., Meyers, S.: Design of optimal water distribution networks. J. Pipeline Div. 94(1), 1\u201310 (1968)","journal-title":"J. Pipeline Div."},{"key":"2029_CR19","volume-title":"Handbook of Natural Gas Engineering","author":"DLV Katz","year":"1959","unstructured":"Katz, D.L.V.: Handbook of Natural Gas Engineering. McGraw-Hill, New York (1959)"},{"key":"2029_CR20","doi-asserted-by":"publisher","unstructured":"Lenz, R.: Optimization of stationary expansion planning and transient network control by mixed-integer nonlinear programming. Ph.D. thesis, Technische Universit\u00e4t Berlin (2021). https:\/\/doi.org\/10.14279\/depositonce-12765","DOI":"10.14279\/depositonce-12765"},{"issue":"1","key":"2029_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00291-021-00648-7","volume":"44","author":"R Lenz","year":"2021","unstructured":"Lenz, R., Becker, K.H.: Optimization of capacity expansion in potential-driven networks including multiple looping: a comparison of modelling approaches. OR Spectrum 44(1), 179\u2013224 (2021). https:\/\/doi.org\/10.1007\/s00291-021-00648-7","journal-title":"OR Spectrum"},{"issue":"2","key":"2029_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-020-00974-0","volume":"80","author":"F Liers","year":"2021","unstructured":"Liers, F., Martin, A., Merkert, M., Mertens, N., Michaels, D.: Solving mixed-integer nonlinear optimization problems using simultaneous convexification: a case study for gas networks. J. Global Optim. 80(2), 1\u201334 (2021). https:\/\/doi.org\/10.1007\/s10898-020-00974-0","journal-title":"J. Global Optim."},{"issue":"2","key":"2029_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10107-005-0582-7","volume":"103","author":"J Linderoth","year":"2005","unstructured":"Linderoth, J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103(2), 251\u2013282 (2005). https:\/\/doi.org\/10.1007\/s10107-005-0582-7","journal-title":"Math. Program."},{"issue":"2","key":"2029_CR24","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10898-018-0626-1","volume":"72","author":"M Locatelli","year":"2018","unstructured":"Locatelli, M.: Convex envelopes of bivariate functions through the solution of KKT systems. J. Global Optim. 72(2), 277\u2013303 (2018). https:\/\/doi.org\/10.1007\/s10898-018-0626-1","journal-title":"J. Global Optim."},{"issue":"1","key":"2029_CR25","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part 1\u2014convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976)","journal-title":"Math. Program."},{"key":"2029_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01691-6","author":"B M\u00fcller","year":"2021","unstructured":"M\u00fcller, B., Mu\u00f1oz, G., Gasse, M., Gleixner, A., Lodi, A., Serrano, F.: On generalized surrogate duality in mixed-integer nonlinear programming. Math. Program. (2021). https:\/\/doi.org\/10.1007\/s10107-021-01691-6","journal-title":"Math. Program."},{"issue":"1","key":"2029_CR27","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/110827387","volume":"23","author":"AU Raghunathan","year":"2013","unstructured":"Raghunathan, A.U.: Global optimization of nonlinear network design. SIAM J. Optim. 23(1), 268\u2013295 (2013). https:\/\/doi.org\/10.1137\/110827387","journal-title":"SIAM J. Optim."},{"key":"2029_CR28","series-title":"Princeton Mathematical Series","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)"},{"key":"2029_CR29","doi-asserted-by":"publisher","unstructured":"Schmidt, M., A\u00dfmann, D., Burlacu, R., Humpola, J., Joormann, I., Kanelakis, N., Koch, T., Oucherif, D., Pfetsch, M.E., Schewe, L., Schwarz, R., Sirvent, M.: Gaslib\u2014a library of gas network instances. Data 2(4) (2017). https:\/\/doi.org\/10.3390\/data2040040","DOI":"10.3390\/data2040040"},{"issue":"1","key":"2029_CR30","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF02283695","volume":"25","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Alameddine, A.: An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes. Ann. Oper. Res. 25(1), 197\u2013209 (1990)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"2029_CR31","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1016\/j.ejor.2016.01.008","volume":"252","author":"N Shiono","year":"2016","unstructured":"Shiono, N., Suzuki, H.: Optimal pipe-sizing problem of tree-shaped gas distribution networks. Eur. J. Oper. Res. 252(2), 550\u2013560 (2016). https:\/\/doi.org\/10.1016\/j.ejor.2016.01.008","journal-title":"Eur. J. Oper. Res."},{"issue":"4\u20135","key":"2029_CR32","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/S0098-1354(98)00286-5","volume":"23","author":"EM Smith","year":"1999","unstructured":"Smith, E.M., Pantelides, C.C.: A symbolic reformulation\/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4\u20135), 457\u2013478 (1999)","journal-title":"Comput. Chem. Eng."},{"key":"2029_CR33","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1023\/A:1011233805045","volume":"20","author":"M Tawarmalani","year":"2001","unstructured":"Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Global Optim. 20, 137\u2013158 (2001)","journal-title":"J. Global Optim."},{"key":"2029_CR34","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s10107-002-0308-z","volume":"93","author":"M Tawarmalani","year":"2002","unstructured":"Tawarmalani, M., Sahinidis, N.V.: Convex extensions and convex envelopes of lower semi-continuous functions. Math. Program. 93, 247\u2013263 (2002)","journal-title":"Math. Program."},{"key":"2029_CR35","unstructured":"Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. thesis, Humboldt-Universit\u00e4t zu Berlin (2012)"},{"issue":"1","key":"2029_CR36","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25\u201357 (2006)","journal-title":"Math. Program."},{"key":"2029_CR37","unstructured":"Walski, T.M., Chase, D.V., Savic, D.A.: Water distribution modeling. Tech. rep., University of Dayton, Civil and Environmental Engineering and Engineering Mechanics Faculty Publications, Paper 17 (2001)"},{"issue":"1349","key":"2029_CR38","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1115\/1.4059982","volume":"34","author":"TR Weymouth","year":"1912","unstructured":"Weymouth, T.R.: Problems in natural gas engineering. Trans. Am. Soc. Mech. Eng. 34(1349), 185\u2013231 (1912)","journal-title":"Trans. Am. Soc. Mech. Eng."},{"key":"2029_CR39","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-1-4612-4380-9_16","volume-title":"Breakthroughs in Statistics","author":"F Wilcoxon","year":"1992","unstructured":"Wilcoxon, F.: Individual comparisons by ranking methods. In: Kotz, S., Johnson, N.L. (eds.) Breakthroughs in Statistics, pp. 196\u2013202. Springer, Berlin (1992)"},{"issue":"3","key":"2029_CR40","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1008312714792","volume":"14","author":"JM Zamora","year":"1999","unstructured":"Zamora, J.M., Grossmann, I.E.: A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. J. Global Optim. 14(3), 217\u2013249 (1999)","journal-title":"J. Global Optim."},{"issue":"3","key":"2029_CR41","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/S1052623493260696","volume":"6","author":"J Zhang","year":"1996","unstructured":"Zhang, J., Zhu, D.: A bilevel programming method for pipe network optimization. SIAM J. Optim. 6(3), 838\u2013857 (1996). https:\/\/doi.org\/10.1137\/S1052623493260696","journal-title":"SIAM J. Optim."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02029-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-022-02029-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02029-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T19:55:44Z","timestamp":1727034944000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-022-02029-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["2029"],"URL":"https:\/\/doi.org\/10.1007\/s10957-022-02029-8","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"assertion":[{"value":"13 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}