A two-stage network interdiction-monitoring game

Di H. Nguyen, Yongjia Song, J. Cole Smith

Research output: Contribution to journalArticlepeer-review


We study a network interdiction problem involving two agents: a defender and an evader. The evader seeks to traverse a path from a source node to a terminus node in a directed network without being detected. The game takes place in two stages. In the first stage, the defender removes a set of arcs in the network. In the second stage, the defender and evader play a simultaneous game. The defender monitors a set of arcs, thus increasing the probability that the evader will be detected on that arc (if the evader uses the arc). The evader selects a source-terminus path. Because the second stage is played simultaneously, both agents use mixed-strategy solutions. We approach the solution of the second-stage problem by proposing a constraint-and-column generation algorithm. We show that both the constraint-generation and column-generation problems are NP-hard. Accordingly, we prescribe approximate versions of these problems that can be solved more efficiently. Our algorithm relies on solving the approximate versions until it is necessary to obtain an exact solution of the constraint-generation and column-generation problems. Then, to link the first- and second-stage problems, we model the original problem using an epigraph reformulation, which we solve using a Benders-decomposition based approach. The efficacy of our approach is demonstrated on a set of randomly generated test instances.

Original languageEnglish (US)
Pages (from-to)334-358
Number of pages25
Issue number3
StatePublished - Apr 2023


  • Benders decomposition
  • constraint-and-column generation
  • network interdiction
  • nonlinear programming
  • simultaneous game

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'A two-stage network interdiction-monitoring game'. Together they form a unique fingerprint.

Cite this