Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A reformulation-enumeration MINLP algorithm for gas network design

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Gas networks are used to transport natural gas, which is an important resource for both residential and industrial customers throughout the world. The gas network design problem is generally modelled as a nonconvex mixed-integer nonlinear integer programming problem (MINLP). The challenges of solving the resulting MINLP arise due to the nonlinearity and nonconvexity. In this paper, we propose a framework to study the “design variant” of the problem in which the variables are the diameter choices of the pipes, the flows, the potentials, and the states of various network components. We utilize a nested loop that includes a two-stage procedure that involves a convex reformulation of the original problem in the inner loop and an efficient enumeration scheme in the outer loop. We conduct experiments on benchmark networks to validate and analyze the performance of our framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2

Similar content being viewed by others

References

  1. EIA, U.S.: Natural Gas Explained. https://www.eia.gov/energyexplained/natural-gas/natural-gas-pipelines.php. Accessed 21 Apr 2022 (2021)

  2. Sullivan, S., Dlin, S.: Year in Pipelines: Growth in US Natural Gas Pipeline Assets Slowed Again in 2020. https://www.spglobal.com/marketintelligence/en/news-insights/latest-news-headlines/year-in-pipelines-growth-in-us-natural-gas-pipeline-assetsslowed-again-in-2020-66386728. Accessed 21 Apr 2022 (2021)

  3. Wolf, D.D., Smeers, Y.: Optimal dimensioning of pipe networks with application to gas transmission networks. Oper. Res. 44(4), 596–608 (1996)

    Article  Google Scholar 

  4. Wolf, D.D., Smeers, Y.: The gas transmission problem solved by an extension of the simplex algorithm. Manag. Sci. 46(11), 1454–1465 (2000)

    Article  Google Scholar 

  5. Schmidt, M., Assmann, D., Burlacu, R., Humpola, J., Joormann, I., Kanelakis, N., Koch, T., Oucherif, D., Pfetsch, M.E., Schewe, L., Schewarz, R., Sirvent, M.: Gaslib - a library of gas network instances. Data 2(4), 40 (2015). https://doi.org/10.3390/data2040040

    Article  Google Scholar 

  6. Rio-Mercado, R.Z., Borraz-Sanchez, C.: Optimization problems in natural gas transportation systems: a state-of-the-art review. Appl. Energy 147, 536–555 (2015)

    Article  Google Scholar 

  7. Zheng, Q.P., Rebennack, S., Iliadis, N.A., Pardalos, P.: Optimization Models in the Natural Gas Industry. In: Pardalos, P.M., Rebennack, S., Pereira, M.V.F., Iliadis, N.A. (eds.) Handbook of Power Systems I. Springer, Heidebergy (2010)

    Google Scholar 

  8. Hante, F.M., Schmidt, M.: Gas transport network optimization: mixed-integer nonlinear models. Optimization-online (2023)

  9. 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. Glob. Optim. 80, 307–340 (2021)

    Article  MathSciNet  Google Scholar 

  10. Pfetsch, M.E., Fugenschuh, A., Geibler, B., Geibler, N., Gollmer, R., Hiller, B., Humpola, J., Koch, T., Lehmann, T., Martin, A., Morsi, A., Rovekamp, J., Schewe, L., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Stangl, C., Steinbach, M.C., Vigerske, S., Willert, B.M.: Validation of nominations in gas network optimization: models, methods, and solutions. Optim. Methods Softw. 30(1), 15–53 (2015)

  11. Geibler, 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)

    Article  Google Scholar 

  12. Geibler, B., Morsi, A., Schewe, L., Schmidt, M.: Solving highly detailed gas transport minlps: block separability and penalty alternating direction methods. INFORMS J. Comput. 30(2), 309–323 (2018)

    Article  MathSciNet  Google Scholar 

  13. Burlacu, R., Geissler, B., Schewe, L.: Solving mixed-integer nonlinear programs using adaptively refined mixed-integer linear programmes. Optim. Methods Soft. 35(1), 37–64 (2020)

    Article  Google Scholar 

  14. Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L. (eds.): Evaluating Gas Network Capacities. Society for Industrial and Applied Mathematics, Philadelphia, PA (2015). https://doi.org/10.1137/1.9781611973693

    Book  Google Scholar 

  15. Rose, D., Schmidt, M., Steinbach, M.C., Willert, B.M.: Computational optimization of gas compressor stations: Minlp models versus continuous reformulations. Math. Meth. Oper. Res. 83, 409–444 (2016)

    Article  MathSciNet  Google Scholar 

  16. Schmidt, M., Steinbach, M.C., Willert, B.M.: High detail stationary optimization models for gas networks: validation and results. Optim. Eng. 17, 437–472 (2016)

    Article  MathSciNet  Google Scholar 

  17. Babonneau, F., Nesterov, Y., Vial, J.-P.: Design and operations of gas transmission networks. Oper. Res. 60(1), 34–47 (2012)

    Article  MathSciNet  Google Scholar 

  18. Borraz-Sanchez, C., Bent, R., Backhaus, S., Hijazi, H., Hentenryck, P.V.: Convex relaxations for gas expansion planning. INFORMS J. Comput. 28, 645–656 (2016)

    Article  MathSciNet  Google Scholar 

  19. Zhang, J., Zhu, D.: A bilevel programming method for pipe network optimization. SIAM J. Optim. 6(3), 838–857 (1996)

    Article  MathSciNet  Google Scholar 

  20. Shiono, N., Suzuki, H.: Optimal pipe-sizing problem of tree-shaped gas distribution networks. Eur. J. Oper. Res. 252(2), 550–560 (2016)

    Article  MathSciNet  Google Scholar 

  21. Robinius, M., Schewe, L., Schmidt, M., Stolten, D., Thürauf, J., Welder, L.: Robust optimal discrete arc sizing for tree-shaped potential networks. Comput. Optim. Appl. 73, 791–819 (2019)

    Article  MathSciNet  Google Scholar 

  22. Cherry, C.: Some general theorems for non-linear systems possessing reactance. Philos. Mag. 42(7), 1161–1177 (1951)

    Article  MathSciNet  Google Scholar 

  23. Collins, M., Cooper, L., Helgason, R., Kennington, J., LeBlanc, L.: Solving the pipe network analysis problem using optimization techniques. Manag. Sci. 24(7), 747–760 (1977/78)

  24. Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0–1 mixed integer programs. Math. Program. 106, 225–236 (2006)

    Article  MathSciNet  Google Scholar 

  25. Günlük, O., Linderoth, J.: Perspective reformulation of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183–205 (2010)

    Article  MathSciNet  Google Scholar 

  26. D’Ambrosio, C., Lodi, A., Wiese, S., Bragalli, C.: Mathematical programming techniques in water network optimization. Eur. J. Oper. Res. 243, 774–788 (2015)

    Article  MathSciNet  Google Scholar 

  27. Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., Toth, P.: Water network design by minlp. IBM Res. Rep. RC24495 (W0802-056) (2008)

  28. Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., Toth, P.: On the optimal design of water distribution networks:a practical minlp approach. Optim. Eng. 13, 219–246 (2012)

    Article  MathSciNet  Google Scholar 

  29. Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., Toth, P.: An minlp solution method for a water network problem. In: Azar, Y., Erlebach, T. (eds.) Algorithms - ESA 2006, pp. 696–707. Springer, Berlin, Heidelberg (2006)

    Chapter  Google Scholar 

  30. Humpola, J.: Gas Network Optimization by minlp. PhD Dissertation (2014)

  31. Raghunathan, A.U.: Global optimization of nonlinear network design. SIAM J. Optim. 23(1), 268–295 (2013)

    Article  MathSciNet  Google Scholar 

  32. Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005)

    Article  MathSciNet  Google Scholar 

  33. Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10, 383–421 (2018)

    Article  MathSciNet  Google Scholar 

  34. Achterberg, T.: Scip: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)

    Article  MathSciNet  Google Scholar 

  35. Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The Scip Optimization Suite 7.0. Technical Report, Optimization Online (March 2020). http://www.optimization-online.org/DB_HTML/2020/03/7705.html

  36. ApS, M.: The MOSEK Optimization Toolbox for Python Manual. Version 9.3.10. (2022)

  37. Gurobi Optimization, L.: Gurobi Optimizer Reference Manual (2022)

  38. Sahinidis, N.V.: BARON 22.9.1: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual (2022)

Download references

Acknowledgements

This work was conducted as part of the Institute for the Design of Advanced Energy Systems (IDAES) with support through the Simulation-Based Engineering, Crosscutting Research Program and the Solid Oxide Fuel Cell Program’s Integrated Energy Systems thrust within the U.S. Department of Energy’s Office of Fossil Energy and Carbon Management.

Author information

Authors and Affiliations

  1. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

    Yijiang Li, Santanu S. Dey & Nikolaos V. Sahinidis

  2. School of Chemical and Biomolecular Engineering, Georgia Institute of Technology, Atlanta, USA

    Nikolaos V. Sahinidis

Authors
  1. Yijiang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Santanu S. Dey
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Santanu S. Dey.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Proof of Theorem 1

Proof

We first consider the if part. Suppose that \((\hat{q}^+, \hat{q}^-, \hat{\lambda }, \hat{\mu }^+, \hat{\mu }^-)\) solves (CVXNLP). Consider the first-order stationary conditions for (CVXNLP) as follows:

$$\begin{aligned}&\phi (\hat{q}_a^+) - \hat{\mu }_a^+ - \hat{\lambda }_v + \hat{\lambda }_w = 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A1)
$$\begin{aligned}&\phi (\hat{q}_a^-) - \hat{\mu }_a^- + \hat{\lambda }_v - \hat{\lambda }_w = 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A2)
$$\begin{aligned}&\hat{q}_a^+, \hat{\mu }_a^+ \ge 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A3)
$$\begin{aligned}&\hat{q}_a^+ \cdot \hat{\mu }_a^+ = 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A4)
$$\begin{aligned}&\hat{q}_a^-, \hat{\mu }_a^- \ge 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A5)
$$\begin{aligned}&\hat{q}_a^- \cdot \hat{\mu }_a^- = 0, \qquad a = (v,w) \in A_p{,} \end{aligned}$$
(A6)
$$\begin{aligned}&\sum _{a \in {A_\text {in}(v)}} (\hat{q}_a^+ - \hat{q}_a^-) - \sum _{a \in {A_\text {out}(v)}} (\hat{q}_a^+ - \hat{q}_a^-) = d_v, \; v \in \mathcal {V}. \end{aligned}$$
(A7)

First, it cannot happen that \(\hat{q}_a^+, \hat{q}_a^- > 0\) for any \(a \in A_p\), otherwise, we can define

$$\begin{aligned} \tilde{q}_a^+ = \max \{\hat{q}_a^+ - \hat{q}_a^-, 0\}, \; \tilde{q}_a^- = \max \{0, \hat{q}_a^- - \hat{q}_a^+\}, \end{aligned}$$
(A8)

where \(\tilde{q}_a^+ \le \hat{q}_a^+\) and \(\tilde{q}_a^- \le \hat{q}_a^-\). The new flow values \(\tilde{q}_a^+\) and \(\tilde{q}_a^-\) are feasible and because of the strict monotonicity of \(\phi (\cdot )\), they result in a smaller objective value which contradicts the optimality of \(\hat{q}^+\) and \(\hat{q}^-\). Furthermore, the complementary slackness conditions imply that, if \(\hat{q}_a^+ \; (\text {or} \; \hat{q}_a^-) > 0\), then \(\hat{\mu }_a^+ \; (\text {or} \; \hat{\mu }_a^-) = 0\). If \(\hat{q}_a^+ = \hat{q}_a^- = 0\) for some a, then adding (A1) and (A2) gives

$$\begin{aligned} \hat{\mu }_a^+ + \hat{\mu }_a^- = 0 \implies \hat{\mu }_a^+ = \hat{\mu }_a^- = 0. \end{aligned}$$
(A9)

Consequently, we can simplify (A1) and (A2) by differentiating the cases on \(q_a^+\) and \(q_a^-\) to be

$$\begin{aligned}&\phi (\hat{q}_a^+) - \hat{\lambda }_v + \hat{\lambda }_w = 0, \qquad a = (v,w) : \hat{q}_a^+ > 0{,} \end{aligned}$$
(A10)
$$\begin{aligned}&\phi (\hat{q}_a^-) + \hat{\lambda }_v - \hat{\lambda }_w = 0, \qquad a = (v,w): \hat{q}_a^- > 0{,} \end{aligned}$$
(A11)
$$\begin{aligned}&\hat{\lambda }_v - \hat{\lambda }_w = 0, \qquad a = (v,w): \hat{q}_a^+ = \hat{q}_a^- = 0. \end{aligned}$$
(A12)

Now define \((\pi , q)\) as

$$\begin{aligned}&\pi _v = \hat{\lambda }_v, \qquad v \in \mathcal {V}{,} \end{aligned}$$
(A13)
$$\begin{aligned}&q_a = \hat{q}_a^+ - \hat{q}_a^- , \qquad a \in A_p, \end{aligned}$$
(A14)

and we see \((\pi , q)\) satisfies the network analysis equations.

Now we consider the only if part. Suppose that \((\pi , q)\) solves the network analysis equations. We define the following:

$$\begin{aligned}&\hat{q}_a^+ = \max \{0, q_a\}, \qquad a \in A_p{,} \end{aligned}$$
(A15)
$$\begin{aligned}&\hat{q}_a^- = \vert \min \{0, q_a\} \vert , \qquad a \in A_p{,} \end{aligned}$$
(A16)
$$\begin{aligned}&\hat{\lambda }_v = \pi _v, \qquad v \in \mathcal {V}{,} \end{aligned}$$
(A17)
$$\begin{aligned}&\hat{\mu }_a^+ = \max \{0, \pi _w - \pi _v + \phi (\hat{q}_a^+)\}, \qquad a = (v, w) \in A_p{,} \end{aligned}$$
(A18)
$$\begin{aligned}&\hat{\mu }_a^- = \max \{0, \pi _v - \pi _w + \phi (\hat{q}_a^-)\}, \qquad a = (v, w) \in A_p. \end{aligned}$$
(A19)

Then \((\hat{q}^+, \hat{q}^-, \hat{\lambda }, \hat{\mu }^+, \hat{\mu }^-)\) satisfies the first-order stationary conditions. To see this, we first verify that, when \(q_a \ge 0\), then \(\hat{q}_a^+ = q_a \ge 0\) and \(\hat{q}_a^ - = 0\). From the potential loss equation (42) in network analysis equations, we have that: \(\pi _v - \pi _w = \phi (q_a) = \phi (\hat{q}_a^+)\). Consequently, we have

$$\begin{aligned} \hat{\mu }_a^+&= \max \{0, \pi _w - \pi _v + \phi (\hat{q}_a^+)\} = 0{,} \end{aligned}$$
(A20)
$$\begin{aligned} \hat{\mu }_a^-&= \max \{0, \pi _v - \pi _w + \phi (\hat{q}_a^-)\} = \max \{0, \phi (\hat{q}_a^+) + \phi (0)\} = \phi (\hat{q}_a^+) \ge 0, \end{aligned}$$
(A21)

and

$$\begin{aligned}&\phi (\hat{q}_a^+) - \hat{\mu }_a^+ - \hat{\lambda }_v + \hat{\lambda }_w = \phi (\hat{q}_a^+) - 0 - \pi _v + \pi _w = 0{,} \end{aligned}$$
(A22)
$$\begin{aligned}&\phi (\hat{q}_a^-) - \hat{\mu }_a^- + \hat{\lambda }_v - \hat{\lambda }_w = \phi (0) - \phi (\hat{q}_a^+) + \pi _v - \pi _w = 0. \end{aligned}$$
(A23)

Similarly, we can verify for \(q_a < 0\). Furthermore, the strict monotonically increasing property of \(\phi (\cdot )\) implies the convexity of \(\Phi (\cdot )\). The constraints in (CVXNLP) are linear and thus (CVXNLP) is convex. The satisfaction of the first-order stationary conditions is necessary and sufficient for \((\pi , q)\) to be an optimal solution to (CVXNLP) and it is the unique optimal solution due to the convexity. \(\square \)

Mixed-integer second-order cone (MISOC) relaxation

The relaxations are constructed for the pipes and resistors. For the pipes, instead of decomposing the flow variables \(q_{a,i}\) into \(q_{a,i}^+\) and \(q_{a,i}^-\), we define two binary variables \(x_{a}^+\) and \(x_a^-\) for the flow directions and enforce \(x_a^+ + x_a^- = 1\). If \(x_a^+ = 1\), then \(q_{a,i} \ge 0\) and if \(x_a^- = 1\), then \(q_{a,i} < 0\). In addition, we create multiple potential variables \(\pi _{v,i}\) and \(\pi _{w,i}\) for \(a = (v,w) \in A_p\) and \(i \in [n]\). Now consider a pipe \(a = (v,w)\) and a diameter choice i, we can write the potential loss as

$$\begin{aligned} (x_a^+ - x_a^-)(\pi _{v,i} - \pi _{w,i}) = \alpha _{a,i}q_{a,i}^2. \end{aligned}$$
(B24)

The left-hand side of (B24) is bilinear. If we define \(\gamma _{a,i} = (x_a^+ - x_a^-)(\pi _{v,i} - \pi _{w,i})\), we can write the standard McCormick relaxation for \(\gamma _{a,i} = (x_a^+ - x_a^-)(\pi _{v,i} - \pi _{w,i})\) by

$$\begin{aligned}&\gamma _{a,i} \ge \pi _{w,i} - \pi _{v,i} + (\pi _v^\text {min} - \pi _w^\text {max})(x_a^+ - x_a^- + 1){,} \end{aligned}$$
(B25)
$$\begin{aligned}&\gamma _{a,i} \ge \pi _{v,i} - \pi _{w,i} + (\pi _v^\text {max} - \pi _w^\text {min})(x_a^+ - x_a^- - 1){,} \end{aligned}$$
(B26)
$$\begin{aligned}&\gamma _{a,i} \ge \pi _{w,i} - \pi _{v,i} + (\pi _v^\text {max} - \pi _w^\text {min})(x_a^+ - x_a^- + 1){,} \end{aligned}$$
(B27)
$$\begin{aligned}&\gamma _{a,i} \ge \pi _{v,i} - \pi _{w,i} + (\pi _v^\text {min} - \pi _w^\text {max})(x_a^+ - x_a^- - 1). \end{aligned}$$
(B28)

With \(\gamma _{a,i}\) defined, constraint (B24) can be written as \(\gamma _{a,i} = \alpha _{a,i}q_{a,i}^2\) and can be further relaxed to become convex as follows:

$$\begin{aligned} \gamma _{a,i} \ge \alpha _{a,i}q_{a,i}^2. \end{aligned}$$
(B29)

Applying perspective strengthening to the relaxed constraint gives

$$\begin{aligned} z_{a,i} \gamma _{a,i} \ge \alpha _{a,i}q_{a,i}^2. \end{aligned}$$
(B30)

Now the potential loss constraint (18) for pipes becomes

$$\begin{aligned} \pi _v - \pi _w = \sum _{i \in [n]} \gamma _{a,i}. \end{aligned}$$
(B31)

We can create similar relaxations for the resistors. For a resistor \(a = (v,w) \in A_r\), we have

$$\begin{aligned}&\gamma _{a} \ge \pi _{w} - \pi _{v} + (\pi _v^\text {min} - \pi _w^\text {max})(x_a^+ - x_a^- + 1){,} \end{aligned}$$
(B32)
$$\begin{aligned}&\gamma _{a} \ge \pi _{v} - \pi _{w} + (\pi _v^\text {max} - \pi _w^\text {min})(x_a^+ - x_a^- - 1){,} \end{aligned}$$
(B33)
$$\begin{aligned}&\gamma _{a} \ge \pi _{w} - \pi _{v} + (\pi _v^\text {max} - \pi _w^\text {min})(x_a^+ - x_a^- + 1){,} \end{aligned}$$
(B34)
$$\begin{aligned}&\gamma _{a} \ge \pi _{v} - \pi _{w} + (\pi _v^\text {min} - \pi _w^\text {max})(x_a^+ - x_a^- - 1){,} \end{aligned}$$
(B35)
$$\begin{aligned}&\gamma _a \ge \alpha _a q_a^2. \end{aligned}$$
(B36)

Additionally, the binary variables \(x_a^\text {dir}\) in constraints (19)-(20) and (26)-(27) that govern flow limits on directions are replaced by \(x_a^+\) and \(x_a^-\) correspondingly. We keep the rest of constraints unchanged and obtain a convex MISOC relaxation of the design problem as a result.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, Y., Dey, S.S. & Sahinidis, N.V. A reformulation-enumeration MINLP algorithm for gas network design. J Glob Optim 90, 931–963 (2024). https://doi.org/10.1007/s10898-024-01424-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-024-01424-x

Keywords

Search

Navigation