Robust Minimum-Cost Flow Problems Under Multiple Ripple Effect Disruptions

Mehdi Ansari (), Juan S. Borrero () and Leonardo Lozano ()
Additional contact information
Mehdi Ansari: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Juan S. Borrero: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Leonardo Lozano: Operations, Business Analytics & Information Systems, University of Cincinnati, Cincinnati, Ohio 45221

INFORMS Journal on Computing, 2023, vol. 35, issue 1, 83-103

Abstract: 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.

Keywords: robust optimization; defender-attacker problems; cut-generation; minimum-cost flow problem; maximal covering location problem; ripple effect disruptions (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1243 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:1:p:83-103

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().