数学优化
线性规划
整数规划
稳健优化
最小成本流问题
流量(数学)
集合(抽象数据类型)
数学
可行区
一般化
计算机科学
流量网络
数学分析
几何学
程序设计语言
作者
Mehdi Ansari,Juan S. Borrero,Leonardo Lozano
出处
期刊:Informs Journal on Computing
日期:2022-10-17
卷期号:35 (1): 83-103
被引量:5
标识
DOI:10.1287/ijoc.2022.1243
摘要
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 .
科研通智能强力驱动
Strongly Powered by AbleSci AI