Authors

Onur Tanil Doganay, Kathrin Klamroth, Bruno Lang, Michael Stiglmayr, Claudia Totzeck

Abstract

We give a short overview of advantages and drawbacks of the classical formulation of minimum cost network flow problems and solution techniques, to motivate a reformulation of classical static minimum cost network flow problems as optimal control problems constrained by port‐Hamiltonian systems (pHS). The first‐order optimality system for the port‐Hamiltonian system‐constrained optimal control problem is formally derived. Then we propose a gradient‐based algorithm to find optimal controls. The port‐Hamiltonian system formulation naturally conserves flow and supports a wide array of further modeling options as, for example, node reservoirs, flow dependent costs, leaking pipes (dissipation) and coupled sub‐networks (ports). They thus provide a versatile alternative to state‐of‐the art approaches towards dynamic network flow problems, which are often based on computationally costly time‐expanded networks. We argue that this opens the door for a plethora of modeling options and solution approaches for network flow problems.

Citation

BibTeX

@article{Doganay_2023,
  title={{Modeling Minimum Cost Network Flows With Port‐Hamiltonian Systems}},
  volume={23},
  ISSN={1617-7061},
  DOI={10.1002/pamm.202200224},
  number={1},
  journal={PAMM},
  publisher={Wiley},
  author={Doganay, Onur Tanil and Klamroth, Kathrin and Lang, Bruno and Stiglmayr, Michael and Totzeck, Claudia},
  year={2023}
}

Download the bib file

References

  • Ford, L. R. & Fulkerson, D. R. Flows in Networks. (1963) doi:10.1515/9781400875184 – 10.1515/9781400875184
  • Cruz‐Mejía, O. & Letchford, A. N. A survey on exact algorithms for the maximum flow and minimum‐cost flow problems. Networks 82, 167–176 (2023) – 10.1002/net.22169
  • Chen, L. et al. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 612–623 (2022) doi:10.1109/focs54457.2022.00064 – 10.1109/focs54457.2022.00064
  • van der Schaft, A. J. & Maschke, B. M. Port-Hamiltonian Systems on Graphs. SIAM J. Control Optim. 51, 906–937 (2013) – 10.1137/110840091
  • Korte, B. & Vygen, J. Combinatorial Optimization. Algorithms and Combinatorics (Springer Berlin Heidelberg, 2018). doi:10.1007/978-3-662-56039-6 – 10.1007/978-3-662-56039-6
  • Fleischer, L. & Skutella, M. Quickest Flows Over Time. SIAM J. Comput. 36, 1600–1630 (2007) – 10.1137/s0097539703427215
  • Pyakurel, U. & Dempe, S. Network Flow with Intermediate Storage: Models and Algorithms. SN Oper. Res. Forum 1, (2020) – 10.1007/s43069-020-00033-0
  • Prasad Pangeni, B. & Nath Dhamala, T. A BRIEF SURVEY ON DYNAMIC NETWORK FLOWS IN CONTINUOUS-TIME MODEL. Journal of Mathematical Sciences & Computational Mathematics 2, 467–477 (2021) – 10.15864/jmscm.2401
  • Köhler, E. & Skutella, M. Flows over Time with Load-Dependent Transit Times. SIAM J. Optim. 15, 1185–1202 (2005) – 10.1137/s1052623403432645
  • Teschl, G. Ordinary Differential Equations and Dynamical Systems. Graduate Studies in Mathematics (2012) doi:10.1090/gsm/140 – 10.1090/gsm/140
  • Tröltzsch, F. Supplementary results on partial differential equations. Graduate Studies in Mathematics 355–383 (2010) doi:10.1090/gsm/112/07 – 10.1090/gsm/112/07