×

zbMATH — the first resource for mathematics

Complementarity-based nonlinear programming techniques for optimal mixing in gas networks. (English) Zbl 1431.90017
Summary: We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we show that classical stationarity concepts are meaningful for the resulting complementarity-based reformulation of the mixing equations. Further, we investigate in a numerical study the performance of this reformulation compared to a more compact complementarity-based one that does not feature such beneficial regularity properties. All computations are performed on publicly available data of real-world size problem instances from steady-state gas transport.

MSC:
90B06 Transportation, logistics and supply chain management
90C20 Quadratic programming
90C11 Mixed integer programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfaki M, Haugland D (2013) Strong formulations for the pooling problem. J Global Optim 56(3):897-916. https://doi.org/10.1007/s10898-012-9875-6 · Zbl 1272.90054
[2] Bard JF (1988) Convex two-level optimization. Math Program 40(1):15-27. https://doi.org/10.1007/BF01580720 · Zbl 0655.90060
[3] Baumrucker BT, Biegler LT (2010) MPEC strategies for cost optimization of pipeline operations. Comput Chem Eng 34(6):900-913. https://doi.org/10.1016/j.compchemeng.2009.07.012
[4] Bertsekas DP (2016) Nonlinear programming. Athena Scientific, Belmont
[5] Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: an integrated package for nonlinear optimization. In: Large scale nonlinear optimization. Springer, Berlin, pp 35-59. https://doi.org/10.1007/0-387-30065-1_4 · Zbl 1108.90004
[6] Conn AR, Gould N, Toint PL (1996) Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization. Math Program. https://doi.org/10.1007/BF02592099 · Zbl 0848.90109
[7] Delfino A, de Oliveira W (2018) Outer-approximation algorithms for nonsmooth convex MINLP problems. Optimization 67(6):797-819. https://doi.org/10.1080/02331934.2018.1434173 · Zbl 1401.90133
[8] Dempe S, Kalashnikov VV, Pérez-Valdés GA, Kalashnykova NI (2011) Natural gas bilevel cash-out problem: convergence of a penalty function method. Eur J Oper Res 215(3):532-538. https://doi.org/10.1016/j.ejor.2011.07.003 · Zbl 1242.90228
[9] Dempe S, Kalashnikov V, Pérez-Valdés GA, Kalashnykova N (2015) Bilevel programming problems: theory, algorithms and application to energy networks. Springer, Berlin. https://doi.org/10.1007/978-3-662-45827-3 · Zbl 1338.90005
[10] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201-213. https://doi.org/10.1007/s101070100263 · Zbl 1049.90004
[11] Ferris MC, Pang JS (1997) Engineering and economic applications of complementarity problems. SIAM Rev 39(4):669-713. https://doi.org/10.1137/S0036144595285963 · Zbl 0891.90158
[12] Fletcher R, Leyffer S (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim Methods Softw 19(1):15-40. https://doi.org/10.1080/10556780410001654241 · Zbl 1074.90044
[13] Fletcher R, Leyffer S, Ralph D, Scholtes S (2006) Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J Optim 17(1):259-286. https://doi.org/10.1137/S1052623402407382 · Zbl 1112.90098
[14] Fügenschuh A, Geißler B, Gollmer R, Morsi A, Pfetsch ME, Rövekamp J, Schmidt M, Spreckelsen K, Steinbach MC (2015) Physical and technical fundamentals of gas networks. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. SIAM-MOS series on optimization, ch 2. SIAM, Philadelphia, pp 17-44. https://doi.org/10.1137/1.9781611973693.ch2
[15] Gamrath G, Fischer T, Gally T, Gleixner AM, Hendel G, Koch T, Maher SJ, Miltenberger M, Müller B, Pfetsch ME, Puchert C, Rehfeldt D, Schenker S, Schwarz R, Serrano F, Shinano Y, Vigerske S, Weninger D, Winkler M, Witt JT, Witzig J (2016) The SCIP optimization suite 3.2. Tech. Rep., ZIB, Takustr.7, 14195, Berlin, 15-60
[16] Geißler B, Martin A, Morsi A, Schewe L (2015a) The MILP-relaxation approach. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. SIAM-MOS series on optimization, ch 6. SIAM, Philadelphia, pp 103-122. https://doi.org/10.1137/1.9781611973693.ch6
[17] Geißler B, Morsi A, Schewe L, Schmidt M (2015b) Solving power-constrained gas transportation problems using an MIP-based alternating direction method. Comput Chem Eng 82:303-317. https://doi.org/10.1016/j.compchemeng.2015.07.005
[18] Geißler B, Morsi A, Schewe L, Schmidt M (2018) Solving highly detailed gas transport MINLPs: block separability and penalty alternating direction methods. INFORMS J Comput 30(2):309-323. https://doi.org/10.1287/ijoc.2017.0780
[19] Grimm V, Grübel J, Schewe L, Schmidt M, Zöttl G (2019) Nonconvex equilibrium models for gas market analysis: failure of standard techniques and alternative modeling approaches. Eur J Oper Res 273(3):1097-1108. https://doi.org/10.1016/j.ejor.2018.09.016 · Zbl 1403.90201
[20] Grimm V, Schewe L, Schmidt M, Zöttl G (2018) A multilevel model of the European entry-exit gas market. Math Methods Oper Res. https://doi.org/10.1007/s00186-018-0647-z · Zbl 1415.90012
[21] Hante FM (2017) Relaxation methods for hyperbolic PDE mixed-integer optimal control problems. Optimal Control Appl Methods 38(6):1103-1110. https://doi.org/10.1002/oca.2315 · Zbl 1386.49047
[22] Hante FM, Leugering G (2009) Optimal boundary control of convention-reaction transport systems with binary control functions. In: Hybrid systems: computation and control. Lecture notes in computer science, vol 5469. Springer, Berlin, pp 209-222. https://doi.org/10.1007/978-3-642-00602-9_15 · Zbl 1237.49006
[23] Hante FM, Leugering G, Martin A, Schewe L, Schmidt M (2017) Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: from modeling to industrial applications. In: Manchanda P, Lozi R, Siddiqi AH (eds) Industrial mathematics and complex systems. Industrial and applied mathematics. Springer, Singapore, pp 77-122. https://doi.org/10.1007/978-981-10-3758-0_5 · Zbl 1396.76078
[24] Hante FM, Sager S (2013) Relaxation methods for mixed-integer optimal control of partial differential equations. Comput Optim Appl 55(1):197-225. https://doi.org/10.1007/s10589-012-9518-3 · Zbl 1272.49026
[25] Hempel AB, Goulart PJ, Lygeros J (2015) Inverse parametric optimization with an application to hybrid system control. IEEE Trans Autom Control 60(4):1064-1069. https://doi.org/10.1109/TAC.2014.2336992 · Zbl 1360.90241
[26] Hempel AB, Goulart PJ, Lygeros J (2017) Strong stationarity conditions for optimal control of hybrid systems. IEEE Trans Autom Control 62(9):4512-4526. https://doi.org/10.1109/TAC.2017.2668839 · Zbl 1390.49023
[27] Hiller B, Humpola J, Lehmann T, Lenz R, Morsi A, Pfetsch ME, Schewe L, Schmidt M, Schwarz R, Schweiger J, Stangl C, Willert BM (2015) Computational results for validation of nominations. In: Koch T, Hiller B, Pfetsch ME, Schewe L (eds) Evaluating gas network capacities. SIAM-MOS series on optimization, ch 12. SIAM, Philadelphia, pp 233-270. https://doi.org/10.1137/1.9781611973693.ch12 · Zbl 1343.90011
[28] 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 (2017) GasLib-a library of gas network instances. Data 2(4). https://doi.org/10.3390/data2040040
[29] Humpola J, Joormann I, Oucherif D, Pfetsch ME, Schewe L, Schmidt M, Schwarz R (2015) GasLib—a library of gas network instances. Technical report. http://www.optimization-online.org/DB_HTML/2015/11/5216.html
[30] Kalashnikov VV, Ríos-Mercado RZ (2006) A natural gas cash-out problem: a bilevel programming framework and a penalty function method. Optim Eng 7(4):403-420. https://doi.org/10.1007/s11081-006-0347-z · Zbl 1178.90256
[31] Koch T, Hiller B, Pfetsch ME, Schewe L (eds) (2015) Evaluating gas network capacities. SIAM-MOS series on optimization. SIAM, Philadelphia, pp xvi + 364. https://doi.org/10.1137/1.9781611973693 · Zbl 1322.90007
[32] Kraemer K, Kossack S, Marquardt W (2007) An efficient solution method for the MINLP optimization of chemical processes. In: Plesu V, Agachi PS (eds) 17th European symposium on computer aided process engineering, computer aided chemical engineering, vol 24. Elsevier, Amsterdam, pp 105-110. https://doi.org/10.1016/S1570-7946(07)80041-1
[33] Kraemer K, Marquardt W (2010) Continuous reformulation of MINLP problems. In: Diehl M, Glineur F, Jarlebring E, Michiels W (eds) Recent advances in optimization and its applications in engineering. Springer, Berlin, pp 83-92. https://doi.org/10.1007/978-3-642-12598-0_8
[34] LaMaTTO++: a framework for modeling and solving mixed-integer nonlinear programming problems on networks (2016). http://www.mso.math.fau.de/edom/projects/lamatto.html. Accessed 7 June 2018
[35] Leyffer S (2018) MacMPEC. https://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC. Accessed 08 June 2018
[36] Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints. Cambridge University Press, Cambridge
[37] McCarl BA (2009) GAMS user guide. Version 23.0
[38] Misener R, Floudas CA (2009) Advances for the pooling problem: modeling, global optimization, and computational studies. Appl Comput Math 8(1):3-22 · Zbl 1188.90287
[39] Misener R, Floudas CA (2014) ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J Global Optim. https://doi.org/10.1007/s10898-014-0166-2 · Zbl 1301.90063
[40] Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer, Berlin. https://doi.org/10.1007/978-0-387-40065-5
[41] Pfetsch ME, Fügenschuh A, Geißler B, Geißler 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 (2015) Validation of nominations in gas network optimization: models, methods, and solutions. Optim Methods Softw 30(1):15-53. https://doi.org/10.1080/10556788.2014.888426 · Zbl 1325.90019
[42] Ríos-Mercado RZ, Borraz-Sánchez C (2015) Optimization problems in natural gas transportation systems: a state-of-the-art review. Appl Energy 147:536-555. https://doi.org/10.1016/j.apenergy.2015.03.017
[43] Rose D, Schmidt M, Steinbach MC, Willert BM (2016) Computational optimization of gas compressor stations: MINLP models versus continuous reformulations. Math Methods Oper Res 83(3):409-444. https://doi.org/10.1007/s00186-016-0533-5 · Zbl 1354.90008
[44] Rüffler F, Hante FM (2016) Optimal switching for hybrid semilinear evolutions. Nonlinear Anal Hybrid Syst 22:215-227. https://doi.org/10.1016/j.nahs.2016.05.001 · Zbl 1346.49033
[45] Sahinidis NV (2014) BARON 14.3.1: global optimization of mixed-integer nonlinear programs, user’s manual
[46] Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math Oper Res 25(1):1-22. https://doi.org/10.1287/moor.25.1.1.15213 · Zbl 1073.90557
[47] Schewe L, Schmidt M (2018) Computing feasible points for binary MINLPs with MPECs. Math Program Comput (Forthcoming) · Zbl 1411.90008
[48] Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. PhD thesis, Leibniz Universität Hannover
[49] Schmidt M, Steinbach MC, Willert BM (2013) A primal heuristic for nonsmooth mixed integer nonlinear optimization. In: Jünger M, Reinelt G (eds) Facets of combinatorial optimization. Springer, Berlin, pp 295-320. https://doi.org/10.1007/978-3-642-38189-8_13 · Zbl 1317.90212
[50] Schmidt M, Steinbach MC, Willert BM (2015) High detail stationary optimization models for gas networks. Optim Eng 16(1):131-164. https://doi.org/10.1007/s11081-014-9246-x · Zbl 1364.90066
[51] Schmidt M, Steinbach MC, Willert BM (2016) High detail stationary optimization models for gas networks: validation and results. Optim Eng 17(2):437-472. https://doi.org/10.1007/s11081-015-9300-3 · Zbl 1364.90067
[52] Stein O, Oldenburg J, Marquardt W (2004) Continuous reformulations of discrete-continuous optimization problems. Comput Chem Eng 28(10):1951-1966. https://doi.org/10.1016/j.compchemeng.2004.03.011
[53] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103(2):225-249. https://doi.org/10.1007/s10107-005-0581-8 · Zbl 1099.90047
[54] van der Hoeven T (2004) Math in gas and the art of linearization. PhD thesis, Rijksuniversiteit Groningen
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.