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. Due to increasing cost pressure, but also due to the availability of powerful software, modern optimization methods are applied frequently to reduce costs and to improve the quality of planning and operation. Many real-world problems in transport and distribution, however, are very complex. A realistic mathematical model of the water network of a larger city, for example, can easily consist of more than 100,000 junctions and pipes. For networks of this size, providing globally optimal solutions or at least good bounds for assessing the quality of an approximate solution is still a big mathematical and computational challenge. Our project addresses this challenge for so-called "potential-driven nonlinear network flow problems", which are a key model for infrastructure networks for fluids such as water or gas. These problems feature a potential for each node, and the flow on an arc is related to the difference of the potentials 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. Beyond potential-driven nonlinear networks, acyclic flows are also relevant for applications in transportation and distribution where the flow direction can be controlled, e. g. in the design of evacuation pathways and traffic routing in multi-lane roads or tunnels. This project studies network flow problems with the additional constraint stipulating that the flows in the network must be acyclic. Analyzing the discrete structure resulting from the combinatorial interplay of the flow conservation in networks with the acyclicity constraint will allow us to (better) tackle the nonconvex mixed integer nonlinear programs (MINLPs) arising in many applications. In particular, we expect to be able to exploit our insights for obtaining improved bounds for the flows and hence tighter convex relaxations of our network flow problems, and for adding stronger constraints for the binary variables encoding the flow direction. Additionally, certain potential-driven network flow problems are easier to solve when the flow direction is fixed. Special-purpose algorithms can exploit this property and insights on feasible arc orientations under the acyclicity constraint. In short the project aims at improving models and algorithms for solving nonconvex potential-driven network flow problems to global optimality, and, by doing so, at contributing to efficient and effective planning and operation of today's utility and infrastructure networks.
