direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Dynamic flows with time-varying network parameters: Optimality conditions and strong duality
Zitatschlüssel Report-015-2010
Autor S. Mehdi Hashemi and Ronald Koch and Ebrahim Nasrabadi and Martin Skutella
Jahr 2010
Nummer 015
Monat jun
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag