×

Convex relaxations for gas expansion planning. (English) Zbl 1355.90063

Summary: Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the nonconvex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, we present a convex mixed-integer second-order cone relaxation for the gas expansion planning problem under steady-state conditions. The underlying model offers tight lower bounds with high computational efficiency. In addition, the optimal solution of the relaxation can often be used to derive high-quality solutions to the original problem, leading to provably tight optimality gaps and, in some cases, global optimal solutions. The convex relaxation is based on a few key ideas, including the introduction of flux direction variables, exact McCormick relaxations, on/off constraints, and integer cuts. Numerical experiments are conducted on the traditional Belgian gas network, as well as other real larger networks. The results demonstrate both the accuracy and computational speed of the relaxation and its ability to produce high-quality solutions.

MSC:

90C25 Convex programming
90C11 Mixed integer programming
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achterberg T (2009) Scip: Solving constraint integer programs. Math. Programming Comput. 1(1):1-41. CrossRef · Zbl 1171.90476
[2] André J (2010) Optimization of investments in gas networks. Ph.D. thesis, School in Business, Université Lille Nord de France, France.
[3] André J, Bonnans F, Cornibert L (2009) Optimization of capacity expansion planning for gas transportation networks. Eur. J. Oper. Res. 197(3):1019-1027. CrossRef · Zbl 1176.90045
[4] Atamturk A (2002) On capacitated network design cut-set polyhedra. Math. Programming 92(3):425-437. CrossRef · Zbl 1008.90003
[5] Babonneau F, Nesterov Y, Vial J-P (2012) Design and operations of gas transmission networks. Oper. Res. 60(1):34-47. Link · Zbl 1242.90033
[6] Bonami P, Lee J (2013) Bonmin, user’s manual. Accessed June 1, 2015, http://www.coin-or.org/bonmin/intro.html.
[7] Bonnans JF, Spiers G, Vie J-L (2011) Global optimization of pipe networks by the interval analysis approach: The Belgium network case. Technical report, Inria Research Report RR-7796, France.
[8] Borraz-Sánchez C (2010) Optimization methods for pipeline transportation of natural gas. Ph.D. thesis, University of Bergen, Bergen, Norway. · Zbl 1277.49043
[9] Boyd ID, Surry PD, Radcliffe NJ (1994) Constrained gas network pipe sizing with genetic algorithms. Accessed May 26, 2016, http://stochasticsolutions.com/pdf/epcctr9411.pdf.
[10] Carter RG (1996) Compressor station optimization: Computational accuracy and speed. Technical report, PSIG Annual Meeting, San Francisco.
[11] Coelho PM, Pinho C (2007) Considerations about equations for steady state flow in natural gas pipelines. J. Braz. Soc. Mech. Sci. Engrg. 29(3):262-273. CrossRef
[12] Correa-Posada CM, Sánchez-Martín P (2014) Security-constrained optimal power and natural-gas flow. IEEE Trans. Power Systems 29(4):1780-1787. CrossRef
[13] de Wolf D, Bakhouya B (2012) Optimal dimensioning of pipe networks: The new situation when the distribution and the transportation functions are disconnected. Klatte D, Schmedders K, eds. Oper. Res. Proc. 2011: Selected Papers Internat. Conf. Oper. Res. (OR 2011), Zurich, 369-374. CrossRef · Zbl 1306.90025
[14] de Wolf D, Smeers Y (1996) Optimal dimensioning of pipe networks with application to gas transmission networks. Oper. Res. 44(4):596-608. Link · Zbl 0865.90042
[15] De Wolf D, Smeers Y (2000) The gas transmission problem solved by an extension of the simplex algorithm. Management Sci. 46(11):1454-1465. Link · Zbl 1232.90355
[16] De Wolf D, Janssens de Bisthoven O, Smeers Y (1991) The simplex algorithm extended to piecewise linearly constrained problems i: The method and an implementation. Technical report, Université catholique de Louvain, Louvain, Belgium.
[17] Drud AS (1994) CONOPT–A large-scale GRG code. ORSA J. Comput. 6(2):207-216. Link · Zbl 0806.90113
[18] Edgar TF, Himmelblau DM, Bickel TC (1978) Optimal design of gas transmission network. Soc. Petroleum Engineers J. 18(2):96-104. CrossRef
[19] Edgar TF, Himmelblau DM, Lasdon LS (2001a) gasnet.gms: Optimal design of a gas transmission network. Accessed June 1, 2015, http://www.gams.com/modlib/libhtml/gasnet.htm.
[20] Edgar TF, Himmelblau DM, Lasdon LS (2001b) Optimization of Chemical Processes, Chapter 9: Mixed-Integer Programming, 2nd ed. (McGraw-Hill, Boston).
[21] Elshiekh TM, Khalil SA, El Mawgoud HA (2013) Optimal design and operation of Egyptian gas-transmission pipelines. Oil Gas Facilities, Soc. Petroleum Engineers 2(4):44-48. CrossRef
[22] Fügenschuh A, Humpola J (2014) A unified view on relaxations for a nonlinear network flow problem. Technical report, Universität der Bundeswehr Hamburg, Germany.
[23] GAMS Development Corporation (2015) GAMS–The Solver Manuals. Accessed June 1, 2015, http://www.gams.com/help/topic/gams.doc/solvers/allsolvers.pdf.
[24] GasLib (2014) A library of gas network instances. Accessed June 1, 2015, http://gaslib.zib.de.
[25] Hansen CT, Madsen K, Nielsen HB (1991) Optimization of pipe networks. Math. Programming 52(1-3):45-58. CrossRef · Zbl 0728.90032
[26] Hijazi H, Bonami P, Cornuéjols G, Ouorou A (2012) Mixed-integer nonlinear programs featuring on/off constraints. Comput. Optim. Appl. 52(2):537-558. CrossRef · Zbl 1250.90058
[27] Humpola J, Fügenschuh A (2014) A new class of valid inequalities for nonlinear network design problems. Angewandte Mathematik und Optimierung Schriftenreihe (AMOS#4), Applied Mathematics and Optimization Series, Universität der Bundeswehr Hamburg, Germany.
[28] Humpola J, Fügenschuh A (2015) Convex reformulations for solving a nonlinear network design problem. Comput. Optim. Appl. 62(3):1-43. CrossRef · Zbl 1337.90072
[29] Humpola J, Fügenschuh A, Koch T (2016) Valid inequalities for the topology optimization problem in gas network design. OR Spectrum 38(3):597-631. CrossRef · Zbl 1372.90023
[30] Humpola J, Fügenschuh A, Lehmann T (2015a) A primal heuristic for optimizing the topology of gas networks based on dual information. EURO J. Comput. Optim. 3(1):53-78. CrossRef · Zbl 1309.90015
[31] Humpola J, Fügenschuh A, Lehmann T, Lenz R, Schwarz R, Schweiger J (2015b) The specialized MINLP approach. Koch T, Hiller B, Pfetsch ME, Schewe L, eds. Evaluating Gas Network Capacities (SIAM, Philadelphia), 123-143. · Zbl 1343.90013
[32] Humpola J, Joormann I, Oucherif D, Pfetsch M, Schewe L, Schmidt M, Schwarz R (2015c) GasLib–A library of gas network instances. Accessed December 1, 2015, http://www.optimization-online.org/DB_HTML/2015/11/5216.html.
[33] ILOG CPLEX Optimization Studio, IBM (2013) CPLEX user’s manual, version 12 release 6. Accessed June 1, 2015, http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.studio.help/pdf/usrcplex.pdf.
[34] Keha AB, de Farias IR Jr, Nemhauser GL (2004) Models for representing piecewise linear cost function. Oper. Res. Lett. 32(1): 44-48. CrossRef · Zbl 1056.90107
[35] Koch T, Hiller B, Pfetsch ME, Schewe L (2015) Evaluating Gas Network Capacities (SIAM, Philadelphia). CrossRef
[36] LINDO Systems (1997) Lingo 3.1 modeling software. Accessed June 1, 2015, http://www.lindo.com/.
[37] Markowitz HM, Manne A (1957) On the solution of discrete programming problems. Econometrica 25(1):84-110. CrossRef · Zbl 0078.34005
[38] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs, part i: Convex underestimating problems. Math. Programming 10(1):147-175. CrossRef · Zbl 0349.90100
[39] Mokhatab S, Poe WA (2012) Natural gas compression.Handbook of Natural Gas Transmission and Processing, 2nd ed. (Gulf Professional Publishing, Elsevier Inc., Walthom, MA). CrossRef
[40] Murtaugh BA, Saunders MA (1983) MINOS 5.5 User’s guide. Technical Report SOL-83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA.
[41] O’Neill RP, Williard M, Wilkins B, Pike R (1979) A mathematical programming model for allocation of natural gas. Oper. Res. 27(5):857-873. Link · Zbl 0422.90045
[42] Osiadacz A (1987) Simulation and Analysis of Gas Networks (Gulf Publishing Company, Houston, TX).
[43] Pfetsch ME, Fügenschuh A, Geißler B, Geißler N, Gollmer R, Hiller B, Humpola J (2015) Validation of nominations in gas network optimization: Models, methods, and solutions. Optim. Methods Software 30(1):15-53. CrossRef · Zbl 1325.90019
[44] Poss M (2011) Models and algorithms for network design problems. Ph.D. thesis, Faculté des Sciences, Département d’Informatique, Université Libre de Bruxelles, Belgium. · Zbl 1345.90100
[45] Raack C (2012) Capacitated network design: Multi-commodity flow formulations, cutting planes, and demand uncertainty. Ph.D. thesis, Technische Universität Berlin, Berlin.
[46] 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. CrossRef
[47] Sardanashvili SA (2005) Computational Techniques and Algorithms (Pipeline Gas Transmission) (FSUE Oil and Gaz, I.M. Gubkin, Russian State University of Oil and Gas). [In Russian].
[48] Soliman FI, Murtagh BA (1982) The solution of large-scale gas pipeline design problems. Engrg. Optim. 6(2):77-83. CrossRef
[49] Thorley ARD, Tiley CH (1987) Unsteady and transient flow of compressible fluids in pipelines–A review of theoretical and some experimental studies. Internat. J. Heat Fluid Flow 8(1):3-15. CrossRef
[50] U.S. Energy Information Administration (2008) Accessed June 1, 2015, http://www.eia.gov/pub/oil_gas/natural_gas/analysis_publications/ngpipeline/develop.html.
[51] Uster H, Dilaveroglu S (2014) Optimization for design and operation of natural gas transmission networks. Appl. Energy 133: 56-69. CrossRef
[52] Vajda S (1961) Mathematical Programming (Addison-Wesley, Reading, MA).
[53] Wachter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25-57. CrossRef · Zbl 1134.90542
[54] Wilson JG, Wallace J, Furey BP (1988) Steady-state optimization of large gas transmission systems. Osiadacz AJ, ed. Simulation and Optimization of Large Systems (Clarendon Press, Oxford, UK), 193-205.
[55] Wolf D (2004) Mathematical properties of formulations of the gas transmission problem. SMG Preprint 94/12, Université catholique de Louvain, Belgium.
[56] Wu S, Ríos-Mercado RZ, Boyd EA, Scott LR (2000) Model relaxations for the fuel cost minimization of steady-state gas pipeline networks. Math. Comput. Modelling 31(2-3):197-220. CrossRef
[57] Zheng QP, Rebennack S, Iliadis NA, Pardalos PM (2010) Optimization models in the natural gas industry. Rebennack S, Pardalos PM, Pereira MVF, Iliadis NA, eds. Handbook of Power Systems I (Springer, Berlin), 121-148. CrossRef · Zbl 1359.90069
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.