Optimal sequential stochastic shortest path interdiction

Juan S. Borrero, Denis Sauré and Natalia Trigo

European Journal of Operational Research, 2025, vol. 326, issue 3, 641-655

Abstract: We consider the periodic interaction between a leader and a follower in the context of network interdiction where, in each period, the leader first blocks (momentarily) passage through a subset of arcs in a network, and then the follower traverses the shortest path in the interdicted network. We assume that arc costs are stochastic and that while their underlying distribution is known to the follower, it is not known by the leader. We cast the problem of the leader, who aims at maximizing the cumulative cost incurred by the evader, using the multi-armed bandit framework. Such a setting differs from the traditional bandit in that the feedback elicited by playing an arm is the reaction of an adversarial agent. After developing a fundamental limit in the achievable performance by any admissible policy, we adapt traditional policies developed for linear bandits to our setting. We show that a critical step in such an adaptation is to ensure that the cost vectors imputed by these algorithms lie within a polyhedron characterizing information that can be collected without noise and in finite time. Within such a polyhedron, the problem can be mapped into a linear bandit. The polyhedron has exponentially many constraints in the worst case, which are indirectly tackled by solving several mathematical programs. We test the proposed policies and relevant benchmarks through a set of numerical experiments. Our results show that the adapted policies can significantly outperform the performance of the base policies at the price of increasing their computational complexity.

Keywords: OR in defence; Combinatorial optimization; Network interdiction; Multi-armed bandits (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725002590
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:326:y:2025:i:3:p:641-655

DOI: 10.1016/j.ejor.2025.04.009

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 ().