Dynamic flows with time-varying network parameters: Optimality conditions and strong duality

S. Mehdi Hashemi, Ronald Koch, Ebrahim Nasrabadi, and Martin Skutella

not available

Dynamic network flows, Continuous linear programming, Augmenting paths and cycles, Optimality conditions, Duality, Cycle-canceling algorithm

Dynamic network flow problems model the temporal evolution of flows over time and also consider changes of network parameters such as capacities, costs, supplies, and demands over time. These problems have been extensively studied in the past beacuse of their important role in real world applications such as transport, traffic, and logistics. This has led to many results, but the more challenging continuous time model still lacks some of the key features such as network related optimality conditions and algorithms that are available in the static case.

The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of several well-known optimality conditions for static network flows. Specifically, we establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of dynamic network flows. The underlying idea is to construct a dual feasible solution that proves optimality when the residual network (with respect to a given flow) contains no dynamic cycles with negative cost. We also discuss a generic negative cycle-canceling algorithm resulting from the corresponding optimality criterion and point out promising directions for future research.

Download as [PDF]