Project heads:
Dr. Benjamin Hiller
/
Prof. Dr. Thorsten Koch
/
Prof. Dr. Martin Skutella
Project members:
Dr. Kai-Helge Becker
Duration: 01.06.2017 - 31.12.2019
Status:
running
Located at:
Konrad-Zuse-Zentrum für Informationstechnik Berlin
Description
Utility and infrastructure networks are at the heart of our daily life
and we are taking their proper working for granted. To provide this
service, network operators face difficult planning and operational
problems. The complexity of the considered optimization problems
increases for several reasons, for instance because geographically
bigger networks are considered or the detail level is increased. For
large networks, providing globally optimal solutions or at least good
bounds for assessing solution quality is still a big challenge.
This project addresses this challenge for so-called
potential-driven nonlinear network flow problems that are a
key model for infrastructure networks for fluids, e.g. water and gas.
These problems feature a so-called
potential for each node,
and the flow on an arc is related to the difference of the potential
of its end nodes. In particular, flow is always directed from higher
to lower potential, i.e. the potentials induce an acylic orientation
of the arcs. This observation is the motivation for this project: We
study network flow problems with the additional requirement of
acyclic flows: If each network arc is oriented in the
direction of flow over this arc, then there is no directed cycle in
the resulting network. This is an interesting combinatorial structure
that arises from nonconvex nonlinear constraints and thus links
combinatorial and continuous optimization.
The aim of this project is to develop algorithmic techniques to
exploit this structure to improve global optimization methods for
large-scale nonlinear flow problems.
http://www.zib.de/projects/acyclic-network-flows
