×

Robust flows over time: models and complexity results. (English) Zbl 1405.90135

Summary: 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 \(\varGamma \) 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(\eta k \log T)\), where \(\eta \) and \(k\) are newly introduced instance characteristics and provide a matching lower bound instance with optimality gap \(\varOmega (\log T)\) and \(\eta = k = 1\). The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.

MSC:

90C35 Programming involving graphs or networks
05C21 Flows in graphs
90C05 Linear programming
90C59 Approximation methods and heuristics in mathematical programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aneja, YP; Chandrasekaran, R; Nair, K, Maximizing residual flow under an arc destruction, Networks, 38, 194-198, (2001) · Zbl 0993.90014 · doi:10.1002/net.10001
[2] Aronson, JE, A survey of dynamic network flows, Ann. Oper. Res., 20, 1-66, (1989) · Zbl 0704.90028 · doi:10.1007/BF02216922
[3] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009) · Zbl 1221.90001 · doi:10.1515/9781400831050
[4] Bertsimas, D; Nasrabadi, E; Stiller, S, Robust and adaptive network flows, Oper. Res., 61, 1218-1242, (2013) · Zbl 1291.90046 · doi:10.1287/opre.2013.1200
[5] Bertsimas, D; Sim, M, Robust discrete optimization and network flows, Math. Program. Ser. B, 98, 49-71, (2003) · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4
[6] Dilworth, RP, A decomposition theorem for partially ordered sets, Ann. Math., 51, 161-166, (1950) · Zbl 0038.02003 · doi:10.2307/1969503
[7] Disser, Y., Matuschke, J.: The complexity of computing a robust flow (2017). arXiv:1704.08241 · Zbl 1260.68412
[8] Du, D; Chandrasekaran, R, The maximum residual flow problem: NP-hardness with two-arc destruction, Networks, 50, 181-182, (2007) · Zbl 1146.90345 · doi:10.1002/net.20188
[9] Ford, LR; Fulkerson, DR, Constructing maximal dynamic flows from static flows, Oper. Res., 6, 419-433, (1958) · doi:10.1287/opre.6.3.419
[10] Fortune, S; Hopcroft, J; Wyllie, J, The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121, (1980) · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2
[11] Grötschel, M; Lovász, L; Schrijver, A, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056 · doi:10.1007/BF02579273
[12] Gupta, UI; Lee, DT; Leung, JT, Efficient algorithms for interval graphs and circular-arc graphs, Networks, 12, 459-467, (1982) · Zbl 0493.68066 · doi:10.1002/net.3230120410
[13] Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85-103. Springer, Berlin (1972)
[14] Koch, R; Nasrabadi, E; Skutella, M, Continuous and discrete flows over time. A general model based on measure theory, Math. Methods Oper. Res., 73, 301-337, (2011) · Zbl 1228.90097 · doi:10.1007/s00186-011-0357-2
[15] Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L.: Evaluating Gas Network Capacities. SIAM, Philadelphia (2015) · Zbl 1322.90007 · doi:10.1137/1.9781611973693
[16] Köhler, E; Skutella, M, Flows over time with load-dependent transit times, SIAM J. Optim., 15, 1185-1202, (2005) · Zbl 1097.90009 · doi:10.1137/S1052623403432645
[17] Matuschke, J., McCormick, T.S., Oriolo, G., Peis, B., Skutella, M.: http://materials.dagstuhl.de/files/15/15412/15412.JannikMatuschke.ExtendedAbstract.pdf (2015)
[18] Skutella, M; Cook, WJ (ed.); Lovász, L (ed.); Vygen, J (ed.), An introduction to network flows over time, 451-482, (2009), Berlin · Zbl 1359.90020 · doi:10.1007/978-3-540-76796-1_21
[19] Wood, RK, Deterministic network interdiction, Math. Comput. Model., 17, 1-18, (1993) · Zbl 0800.90772 · doi:10.1016/0895-7177(93)90236-R
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.