TY - CHAP

T1 - Algorithms for network interdiction and fortification games

AU - Smith, J. Cole

AU - Lim, Churlzu

N1 - Publisher Copyright:
© 2008 Springer Science+Business Media, LLC.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Bilinear programming

KW - Duality

KW - Mixed-integer programming

KW - Network fortification

KW - Network interdiction

KW - Stackelberg games

UR - http://www.scopus.com/inward/record.url?scp=84976488395&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976488395&partnerID=8YFLogxK

U2 - 10.1007/978-0-387-77247-9_24

DO - 10.1007/978-0-387-77247-9_24

M3 - Chapter

AN - SCOPUS:84976488395

T3 - Springer Optimization and Its Applications

SP - 609

EP - 644

BT - Springer Optimization and Its Applications

PB - Springer International Publishing

ER -