Robust Minimum-Cost Flow Problems Under Multiple Ripple Effect Disruptions
研究弧段受多重涟漪效应中断影响的最小成本流问题，决策者需在中断最坏情况下最小化成本，分别针对线性与最大破坏模型提出求解算法，并在真实路网中验证了效率提升。
We study a class of adversarial minimum-cost flow problems where the arcs are subject to multiple ripple effect disruptions that increase their usage cost. The locations of the disruptions’ epicenters are uncertain, and the decision maker seeks a flow that minimizes cost assuming the worst-case realization of the disruptions. We evaluate the damage to each arc using a linear model, where the damage is the cumulative damage of all disruptions affecting the arc; and a maximum model, where the damage is given by the most destructive disruption affecting the arc. For both models, the arcs’ costs after disruptions are represented with a mixed-integer feasible region, resulting in a robust optimization problem with a mixed-integer uncertainty set. The main challenge to solve the problem comes from a subproblem that evaluates the worst-case cost for a given flow plan. We show that for the linear model the uncertainty set can be decomposed into a series of single disruption problems, which leads to a polynomial time algorithm for the subproblem. The uncertainty set of the maximum model, however, cannot be decomposed, and we show that the subproblem under this model is NP-hard. For this case, we further present a big-M free binary reformulation of the uncertainty set based on conflict constraints that results in a significantly smaller formulation with tighter linear programming relaxations. We extend the models by considering a less conservative approach where only a subset of the disruptions can occur and show that the properties of the linear and maximum models also hold in this case. We test our proposed approaches over real road networks and synthetics instances and show that our methods achieve orders of magnitude improvements over a standard approach from the literature. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0236] and the Office of Naval Research [Grant N00014-19-1-2329]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1243 .