Search

Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual flows sent later on. In these networks, node potentials correspond to physical quantities such as pressures or hydraulic heads and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of robust network topologies for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness.

In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations ( $${\text{PDEs}}$$ ). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic $${\text{PDEs}}$$ and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem ( $${\text{MINLP}}$$ ). For the numerical solution of the $${\text{MINLP}}$$ , we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems. Finally, we present two case studies that illustrate the applicability of our approach.

Network flows over time form a fascinating area of research. They model the temporal dynamics of network flow problems occurring in a wide variety of applications. Research in this area has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models. In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.

We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community. We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is the so-called deterministic queuing model that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.

The natural linear programming formulation of the maximum s-t-flow problem in path variables has a dual linear program whose underlying polyhedron is the dominant $${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$$of the s-t-cut polytope. We present a complete characterization of $${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$$with respect to vertices, facets, and adjacency.

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})$ -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.

We analyze teh performance fo evolutionary algorithms on various matroid optimization problems that encompass a vast number of efficiently solvable as well as NP-hard combinatorial optimization problems (including many well-known examples such as minimum spanning tree and maximum bipartite matching). We obtain very promising bounds on the expected running time and quality of the computed solution. Our results establish a better theoretical understanding of why randomized search heuristics yield empirically good results for many real-world problems., Reihe CI; 225-07

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (MkSF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M kSF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed e>0, the computed set of alternatives contains a packing used by a (1−e)-approximate solution. The latter result is based on the observation that (1−e)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the MkSF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.

In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, e.g., telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path. In this paper a generalization of this problem is studied. In the considered flow model, a commodity can be split into a bounded number of chunks which can then be routed on different paths. In contrast to classical (splittable) flows and unsplittable flows, the single-commodity case of this problem is already NP-hard and even hard to approximate. We present approximation algorithms for the single- and multi-commodity case and point out strong connections to unsplittable flows. Moreover, results on the hardness of approximation are presented. In particular, we show that some of our approximation results are in fact best possible, unless P = NP.

We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly NP-hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection.