On Solving Continuous-time Dynamic Network Flows

S. Mehdi Hashemi, Ebrahim Nasrabadi, and Martin Skutella

not available

Dynamic network flows, continuous linear programming, discretization, duality, extreme points, purification.

Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally.

In this paper we study a general class of dynamic network flow problems in the more challenging continuous time model and develop two algorithms based on a discretization approach that compute, or at least converge to optimum solutions. Both algorithms lead to approximate interior solutions, while one would like to have extreme point solutions as these usually have a considerably simpler structure than arbitrary feasible solutions and are more meaningful in practice. We therefore also present a purification algorithm for our dynamic flow problems, that is, an algorithm which given as input an arbitrary feasible solution produces as output an extreme point solution without degrading the objective function value.

Download as [PDF] [ps.gz]