Network interdiction with asymmetric cost uncertainty

Di H. Nguyen and J. Cole Smith

European Journal of Operational Research, 2022, vol. 297, issue 1, 239-251

Abstract: We study a shortest-path interdiction problem in which the interdictor acts first to lengthen a subset of arcs, and an evader acts second to select a shortest path across the network. In this problem, the cost for an evader’s arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The interdictor is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The evader, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. The interdictor’s problem is thus to maximize the expected minimum cost attainable by the evader. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen’s inequality as proposed in an earlier study on a maximum-flow interdiction problem. We also provide several algorithmic strategies for accelerating the convergence of the algorithm and demonstrate their effectiveness on randomly generated instances.

Keywords: Networks; Interdiction; Uncertainty (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721003908
Full text for ScienceDirect subscribers only

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:eee:ejores:v:297:y:2022:i:1:p:239-251

DOI: 10.1016/j.ejor.2021.04.055

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().