Algorithmic Results for Potential-Based Flows: Easy and Hard Cases

Groß M, Pfetsch ME, Schewe L, Schmidt M, Skutella M (2018)

Publication Language: English

Publication Status: Submitted

Publication Type: Journal article

Future Publication Type: Journal article

Publication year: 2018

Journal

Networks Wiley-Blackwell

URI: http://www.optimization-online.org/DB_HTML/2017/08/6185.html

DOI: 10.1002/net.21865

Abstract

Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks.

Authors with CRIS profile

Lars Schewe Economics - Discrete Optimization - Mathematics (EDOM) Martin Schmidt Juniorprofessur für Optimierung von Energiesystemen

Related research project(s)

Energiemarktdesign (EMD) Energie Campus Nürnberg (EnCN2) Jan. 1, 2017 - Dec. 31, 2021 Welfare optimal nominations in gas networks and associated equilibria SFB TRR 154 “Mathematische Modellierung, Simulation und Optimierung am Beispiel von Gasnetzen” Oct. 1, 2016 - June 30, 2018

Involved external institutions

Technische Universität Berlin DE Germany (DE) Technische Universität Darmstadt DE Germany (DE)

How to cite

APA:

Groß, M., Pfetsch, M.E., Schewe, L., Schmidt, M., & Skutella, M. (2018). Algorithmic Results for Potential-Based Flows: Easy and Hard Cases. Networks. https://dx.doi.org/10.1002/net.21865

MLA:

Groß, Martin, et al. "Algorithmic Results for Potential-Based Flows: Easy and Hard Cases." Networks (2018).

BibTeX: Download