Robust flows over time: models and complexity results

DOI10.1007/S10107-017-1170-3MaRDI QIDQ1785195zbMATH OpenOpenAlexFDO

Authors Corinna Gottschalk, Arie M. C. A. Koster, F. Liers, Britta Peis, Daniel Schmand, Andreas Wierz

Publication date 28 September 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06520

zbMATH Keywords

dynamic network flowsoptimality gaptemporally repeated flowsuncertain travel times of flow

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46) Approximation methods and heuristics in mathematical programming (90C59) Flows in graphs (05C21)

Abstract: We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon $T$, while flow requires a certain travel time to traverse an edge. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most $Gamma$ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (that is, without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least $T$. We finally show that the optimality gap is at most $O(etaklogT)$, where $eta$ and $k$ are newly introduced instance characteristics and provide a matching lower bound instance with optimality gap $Omega(logT)$ and $eta=k=1$. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.

Recommendations

• Robust and adaptive network flows
• Flows over Time with Load-Dependent Transit Times
• Robust capacity expansion of network flows
• On robust maximum flow with polyhedral uncertainty sets
• Multicommodity flows over time: Efficient algorithms and complexity

Cites work

• A decomposition theorem for partially ordered sets
• A survey of dynamic network flows
• An introduction to network flows over time
• Constructing maximal dynamic flows from static flows
• Continuous and discrete flows over time
• Degree-constrained orientations of embedded graphs
• Deterministic network interdiction
• Efficient algorithms for interval graphs and circular-arc graphs
• Evaluating Gas Network Capacities
• Flows over Time with Load-Dependent Transit Times
• Maximizing residual flow under an arc destruction
• Reducibility among combinatorial problems
• Robust and adaptive network flows
• Robust discrete optimization and network flows
• Robust optimization
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• The maximum residual flow problem: NP‐hardness with two‐arc destruction

Cited in

(13)

• Robust and adaptive network flows
• Robust resource allocations in temporal networks
• The non-stop disjoint trajectories problem
• Rerouting Flows when Links Fail
• scientific article; zbMATH DE number 5574999 (Why is no real title available?)
• Robust transshipment problem under consistent flow constraints
• The complexity of computing a robust flow
• On robust maximum flow with polyhedral uncertainty sets
• A robust optimization model for distribution network design under a mixed integer set of scenarios
• Towards a theory of continuous flow models
• Polynomial-time identification of robust network flows under uncertain arc failures
• Minimum‐cost flow problems having arc‐activation costs
• Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption

This page was built for publication: Robust flows over time: models and complexity results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785195)