MIP-based instantaneous control of mixed-integer PDE-constrained gas transport problems | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

MIP-based instantaneous control of mixed-integer PDE-constrained gas transport problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations on a graph. We propose an instantaneous control approach in which suitable Euler discretizations yield systems of ordinary differential equations on a graph. This networked system of ordinary differential equations is shown to be well-posed and affine-linear solutions of these systems are derived analytically. As a consequence, finite-dimensional mixed-integer linear optimization problems are obtained for every time step that can be solved to global optimality using general-purpose solvers. We illustrate our approach in practice by presenting numerical results on a realistic gas transport network.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. We remark that the consideration of flexible nodes is not completely in line with the network model presented in Sect. 2 because \(u \in V_- \) or \(u \in V_+ \) for a node \(u \not \in V_0 \) does not hold anymore for all time steps. However, all required changes in the model are straightforward.

  2. http://www.mso.math.fau.de/fileadmin/wima/data_members/schmidt/inst-control.mp4.

References

  1. LaMaTTO++: A Framework for Modeling and Solving Mixed-Integer Nonlinear Programming Problems on Networks (2017). http://www.mso.math.fau.de/edom/projects/lamatto.html

  2. Altmüller, N., Grüne, L., Worthmann, K.: Instantaneous control of the linear wave equation. In: Proceedings of MTNS (2010)

  3. Antil, H., Hintermüller, M., Nochetto, R., Surowiec, T., Wegner, D.: Finite horizon model predictive control of electrowetting on dielectric with pinning. Interfaces Free Bound. 19(1), 1–30 (2017). https://doi.org/10.4171/IFB/375

    Article  MathSciNet  MATH  Google Scholar 

  4. Banda, M.K., Herty, M.: Multiscale modeling for gas flow in pipe networks. Math. Methods Appl. Sci. 31, 915–936 (2008). https://doi.org/10.1002/mma.948

    Article  MathSciNet  MATH  Google Scholar 

  5. Banda, M.K., Herty, M., Klar, A.: Gas flow in pipeline networks. Netw. Heterog. Media 1(1), 41–56 (2006). https://doi.org/10.3934/nhm.2006.1.41

    Article  MathSciNet  MATH  Google Scholar 

  6. Baumrucker, B., Biegler, L.: MPEC strategies for cost optimization of pipeline operations. Comput. Chem. Eng. 34(6), 900–913 (2010). https://doi.org/10.1016/j.compchemeng.2009.07.012

    Article  Google Scholar 

  7. Brouwer, J., Gasser, I., Herty, M.: Gas pipeline models revisited: model hierarchies, nonisothermal models, and simulations of networks. Multiscale Model. Simul. 9(2), 601–623 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Choi, H., Hinze, M., Kunisch, K.: Instantaneous control of backward-facing step flows. Appl. Numer. Math. 31(2), 133–158 (1999). https://doi.org/10.1016/S0168-9274(98)00131-7

    Article  MathSciNet  MATH  Google Scholar 

  9. Choi, H., Temam, R., Moin, P., Kim, J.: Feedback control for unsteady flow and its application to the stochastic burgers equation. J. Fluid Mech. 253, 509–543 (1993). https://doi.org/10.1017/S0022112093001880

    Article  MathSciNet  MATH  Google Scholar 

  10. Coddington, E.A., Carlson, R.: Linear ordinary differential equations. SIAM, Philadelphia (1997)

  11. Domschke, P., Geißler, B., Kolb, O., Lang, J., Martin, A., Morsi, A.: Combination of nonlinear and linear optimization of transient gas networks. INFORMS J. Comput. 23(4), 605–617 (2011). https://doi.org/10.1287/ijoc.1100.0429

    Article  MathSciNet  MATH  Google Scholar 

  12. Ehrhardt, K., Steinbach, M.C.: KKT systems in operative planning for gas distribution networks. Proc. Appl. Math. Mech. 4(1), 606–607 (2004). https://doi.org/10.1002/pamm.200410284

    Article  MATH  Google Scholar 

  13. Ehrhardt, K., Steinbach, M.C., Bock, H.G., Kostina, E., Phu, H.X., Rannacher, R.: Nonlinear optimization in gas networks. In: Bock, H.G., Kostina, E., Phu, H.X., Rannacher, R. (eds.) Modeling, Simulation and Optimization of Complex Processes, pp. 139–148. Springer, Berlin (2005). https://doi.org/10.1007/3-540-27170-8_11

    Chapter  Google Scholar 

  14. Feistauer, M.M.: Mathematical methods in fluid dynamics. Pitman monographs and surveys in pure and applied mathematics. Longman Scientific & Technical New York, Harlow, Essex, England (1993). http://opac.inria.fr/record=b1084590

  15. Geißler, B.: Towards globally optimal solutions for MINLPs by discretization techniques with applications in gas network optimization. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg. (2011)

  16. Geißler, B., Kolb, O., Lang, J., Leugering, G., Martin, A., Morsi, A.: Mixed integer linear models for the optimization of dynamical transport networks. Math. Methods Oper. Res. 73(3), 339–362 (2011). https://doi.org/10.1007/s00186-011-0354-5

    Article  MathSciNet  MATH  Google Scholar 

  17. Geißler, B., Martin, A., Morsi, A., Schewe, L.: Using piecewise linear functions for solving minlps. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, pp. 287–314. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1927-3_10

    Chapter  Google Scholar 

  18. Geißler, B., Martin, A., Morsi, A., Schewe, L.: The MILP-relaxation approach. In: Evaluating Gas Network Capacities [32], chap. 6, pp. https://doi.org/10.1137/1.9781611973693.ch6

  19. Geißler, B., Morsi, A., Schewe, L.: A new algorithm for minlp applied to gas transport energy cost minimization. In: Jünger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, pp. 321–353. Springer, Berlin (2013). https://doi.org/10.1007/978-3-642-38189-8_14

    Chapter  Google Scholar 

  20. Geißler, 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). https://doi.org/10.1016/j.compchemeng.2015.07.005

    Article  Google Scholar 

  21. Geißler, B., Morsi, A., Schewe, L., Schmidt, M.: Solving highly detailed gas transport MINLPs: block separability and penalty alternating direction methods. Tech. rep. (2016). http://www.optimization-online.org/DB_HTML/2016/06/5523.html

  22. Gu, Z., Rothberg, E., Bixby, R.: Gurobi Optimizer Reference Manual, Version 6.5.0 (2015)

  23. Gugat, M.: Boundary controllability between sub- and supercritical flow. SIAM J. Control Optim. 42, 1056–1070 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  24. Gugat, M., Hante, F.M., Hirsch-Dick, M., Leugering, G.: Stationary states in gas networks. Netw. Heterog. Med. 10(2), 295–320 (2015). https://doi.org/10.3934/nhm.2015.10.295

    Article  MathSciNet  MATH  Google Scholar 

  25. Gugat, M., Herty, M., Klar, A., Leugering, G., Schleper, V.: Well-Posedness of Networked Hyperbolic Systems of Balance Laws, pp. 123–146. Springer Basel, Basel (2012). https://doi.org/10.1007/978-3-0348-0133-1_7

    MATH  Google Scholar 

  26. Gugat, M., Herty, M., Schleper, V.: Flow control in gas networks: exact controllability to a given demand. Math. Methods Appl. Sci. 34(7), 745–757 (2011). https://doi.org/10.1002/mma.1394

    Article  MathSciNet  MATH  Google Scholar 

  27. Gugat, M., Leugering, G., Wang, K.: Neumann boundary feedback stabilization for a nonlinear wave equation: a strict \(H^2\)-Lyapunov function. Math. Control Relat. Fields 7(3), 419–448 (2017). https://doi.org/10.3934/mcrf.2017015

    Article  MathSciNet  MATH  Google Scholar 

  28. Hante, F.M., Leugering, G., Martin, A., Schewe, L., Schmidt, M.: 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, A.H. (eds.) Industrial Mathematics and Complex systems: Emerging Mathematical Models, Methods and Algorithms, Industrial and Applied Mathematics (2017). https://opus4.kobv.de/opus4-trr154/files/121/isiam-paper.pdf

  29. Herty, M., Kirchner, C., Klar, A.: Instantaneous control for traffic flow. Math. Methods Appl. Sci. 30(2), 153–169 (2007). https://doi.org/10.1002/mma.779

    Article  MathSciNet  MATH  Google Scholar 

  30. Hinze, M.: Optimal and instantaneous control of the instationary Navier–Stokes equations (2002). https://www.math.uni-hamburg.de/home/hinze/Psfiles/habil_mod.pdf

  31. Hundhammer, R., Leugering, G.: Instantaneous Control of Vibrating String Networks, pp. 229–249. Springer, Berlin (2001). https://doi.org/10.1007/978-3-662-04331-8_15

    MATH  Google Scholar 

  32. Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L.: Evaluating gas network capacities. SIAM-MOS series on optimization. SIAM (2015). https://doi.org/10.1137/1.9781611973693

  33. Kostrykin, V., Schrader, R.: Laplacians on metric graphs: eigenvalues, resolvents and semigroups. In: Quantum graphs and their applications, Contemp. Math., vol. 415, pp. 201–225. Amer. Math. Soc., Providence, RI (2006). https://doi.org/10.1090/conm/415/07870

  34. Lagnese, J.E., Leugering, G., Schmidt, E.J.P.G.: Modeling, Analysis and Control of Dynamic Elastic Multi-link Structures. Birkhäuser, Boston (1994). https://doi.org/10.1007/978-1-4612-0273-8

    Book  MATH  Google Scholar 

  35. Lurie, M.V.: Modeling of Oil Product and Gas Pipeline Transportation. Wiley, New York (2008)

    Book  Google Scholar 

  36. Mahlke, D., Martin, A., Moritz, S.: A simulated annealing algorithm for transient optimization in gas networks. Math. Methods Oper. Res. 66, 99–116 (2007). https://doi.org/10.1007/s00186-006-0142-9

    Article  MathSciNet  MATH  Google Scholar 

  37. Mahlke, D., Martin, A., Moritz, S.: A mixed integer approach for time-dependent gas network optimization. Optim. Methods Softw. 25(4), 625–644 (2010). https://doi.org/10.1080/10556780903270886

    Article  MathSciNet  MATH  Google Scholar 

  38. Martin, A., Möler, M.: Cutting planes for the optimisation of gas networks. In: Bock, H.G., Kostina, E., Phu, H.X., Rannacher, R. (eds.) Modeling, Simulation and Optimization of Complex Processes, pp. 307–330. Springer, Berlin (2005). https://doi.org/10.1007/3-540-27170-8_24

    Chapter  Google Scholar 

  39. Martin, A., Möller, M., Moritz, S.: Mixed integer models for the stationary case of gas network optimization. Math. Program. 105(2), 563–582 (2006). https://doi.org/10.1007/s10107-005-0665-5

    Article  MathSciNet  MATH  Google Scholar 

  40. Morsi, A.: Solving MINLPs on loosely-coupled networks with applications in water and gas network optimization. Ph.D. thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (2013)

  41. Osiadacz, A.J.: Different transient flow models—limitations, advantages, and disadvantages (1996). https://www.onepetro.org/conference-paper/PSIG-9606

  42. Osiadacz, A.J.: Steady state optimisation of gas networks. Arch. Min. Sci. 56(3), 335–352 (2011)

    Google Scholar 

  43. Osiadacz, A.J., Bell, D.J.: Steady-State Optimization of Large Gas Networks, pp. 461–467. Springer, Dordrecht (1990). https://doi.org/10.1007/978-94-009-0629-7_47

    Google Scholar 

  44. Osiadacz, A.J., Chaczykowski, M.: Dynamic control for gas pipeline systems. Arch. Min. Sci. 61(1), 69–82 (2016)

    Google Scholar 

  45. Pellegrino, S., Lanzini, A., Leone, P.: Greening the gas network—the need for modelling the distributed injection of alternative fuels. Renew. Sustain. Energy Rev. 70(Supplement C), 266–286 (2017). https://doi.org/10.1016/j.rser.2016.11.243

    Article  Google Scholar 

  46. Pfetsch, M.E., 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, 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). https://doi.org/10.1080/10556788.2014.888426

    Article  MathSciNet  MATH  Google Scholar 

  47. Ríos-Mercado, R.Z., Borraz-Sánchez, C.: Optimization problems in natural gas transportation systems: a state-of-the-art review. Appl. Energy 147, 536–555 (2015). https://doi.org/10.1016/j.apenergy.2015.03.017

    Article  Google Scholar 

  48. Schmidt, M.: A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Dissertation, Leibniz-Universität Hannover (2013)

  49. Schmidt, M.: An interior-point method for nonlinear optimization problems with locatable and separable nonsmoothness. EURO J. Comput. Optim. 3(4), 309–348 (2015). https://doi.org/10.1007/s13675-015-0039-6. Online first: 09 June 2015

    Article  MathSciNet  MATH  Google Scholar 

  50. Schmidt, M., Steinbach, M.C., Willert, B.M.: A primal heuristic for nonsmooth mixed integer nonlinear optimization. In: Jünger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 295–320. Springer, Berlin (2013). https://doi.org/10.1007/978-3-642-38189-8_13

    Chapter  Google Scholar 

  51. Schmidt, M., Steinbach, M.C., Willert, B.M.: High detail stationary optimization models for gas networks. Optim. Eng. 16(1), 131–164 (2015). https://doi.org/10.1007/s11081-014-9246-x

    Article  MathSciNet  MATH  Google Scholar 

  52. Schmidt, M., Steinbach, M.C., Willert, B.M.: An MPEC based heuristic. In: Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L. (Eds.) Evaluating gas network capacities, SIAM-MOS series on Optimization, chap. 9, pp. 163–180. SIAM (2015). https://doi.org/10.1137/1.9781611973693.ch9

  53. Schmidt, M., Steinbach, M.C., Willert, B.M.: High detail stationary optimization models for gas networks: validation and results. Optim. Eng. 17(2), 437–472 (2016). https://doi.org/10.1007/s11081-015-9300-3

    Article  MathSciNet  MATH  Google Scholar 

  54. Spigler, R., Vianello, M.: Convergence analysis of the semi-implicit Euler method for abstract evolution equations. Numer. Funct. Anal. Optim. 16(5–6), 785–803 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  55. Steinbach, M.C.: On PDE solution in transient optimization of gas networks. J. Comput. Appl. Math. 203(2), 345–361 (2007). https://doi.org/10.1016/j.cam.2006.04.018

    Article  MathSciNet  MATH  Google Scholar 

  56. Zlotnik, A., Chertkov, M., Backhaus, S.: Optimal control of transient flow in natural gas networks. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 4563–4570 (2015). https://doi.org/10.1109/CDC.2015.7402932

Download references

Acknowledgements

We acknowledge funding through the DFG SFB/Transregio 154, Subprojects A05, B07, B08, and C03. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. Finally, we thank Marc Steinbach for the provision of some data that we used for our numerical studies.

Author information

Authors and Affiliations

  1. Lehrstuhl für Angewandte Mathematik 2, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Cauerstr. 11, 91058, Erlangen, Germany

    Martin Gugat, Günter Leugering & David Wintergerst

  2. Discrete Optimization, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Cauerstr. 11, 91058, Erlangen, Germany

    Alexander Martin, Martin Schmidt & Mathias Sirvent

  3. Energie Campus Nürnberg, Fürther Str. 250, 90429, Nuremberg, Germany

    Martin Schmidt

Authors
  1. Martin Gugat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Günter Leugering
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alexander Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Martin Schmidt
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Mathias Sirvent
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. David Wintergerst
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Schmidt.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gugat, M., Leugering, G., Martin, A. et al. MIP-based instantaneous control of mixed-integer PDE-constrained gas transport problems. Comput Optim Appl 70, 267–294 (2018). https://doi.org/10.1007/s10589-017-9970-1

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-017-9970-1

Keywords

Mathematics Subject Classification

Search

Navigation