Algorithms for network interdiction and fortification games

J. Cole Smith, Churlzu Lim

Research output: Chapter in Book/Entry/PoemChapter

56 Scopus citations


This chapter explores models and algorithms applied to a class of Stackelberg games on networks. In these network interdictiongames, a network exists over which an operator wishes to execute some function, such as finding a shortest path, shipping a maximum flow, or transmitting a minimum cost multicommodity flow. The role of the interdictor is to compromise certain network elements before the operator acts, by (for instance) increasing the cost of flow or reducing capacity on an arc. We begin by reviewing the field of network interdiction and its related theoretical and mathematical foundations. We then discuss recent applications of stochastic models, valid inequalities, continuous bilinear programming techniques, and asymmetric analysis to network interdiction problems. Next, note that interdiction problems can be extended to a three-stage problem in which the operator fortifies the network (by increasing capacities, reducing flow costs, or defending network elements from the interdictor) before the interdictor takes action. We devote one section to ongoing research in this area and conclude by discussing areas for future research.

Original languageEnglish (US)
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer International Publishing
Number of pages36
StatePublished - 2008
Externally publishedYes

Publication series

NameSpringer Optimization and Its Applications
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836


  • Bilinear programming
  • Duality
  • Mixed-integer programming
  • Network fortification
  • Network interdiction
  • Stackelberg games

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'Algorithms for network interdiction and fortification games'. Together they form a unique fingerprint.

Cite this