Algorithms for network interdiction and fortification games

J. Cole Smith, Churlzu Lim

Research output: Chapter in Book/Report/Conference proceedingChapter

40 Scopus citations

Abstract

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
Pages609-644
Number of pages36
DOIs
StatePublished - Jan 1 2008
Externally publishedYes

Publication series

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

Keywords

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

ASJC Scopus subject areas

  • Control and Optimization

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

  • Cite this

    Smith, J. C., & Lim, C. (2008). Algorithms for network interdiction and fortification games. In Springer Optimization and Its Applications (pp. 609-644). (Springer Optimization and Its Applications; Vol. 17). Springer International Publishing. https://doi.org/10.1007/978-0-387-77247-9_24