Bilevel Network Interdiction Models: Formulations and Solutions

Author:
Publisher website
Google Scholar
Abstract
Thebilevel network‐interdiction problem(BNI) models the effective use of limited resources, by an “interdictor,” to attack a network that an “enemy” may use to the interdictor's disadvantage. BNI is a two‐person, zero‐sum, sequential‐play (Stackelberg) game with two stages: in the first stage, the interdictor attacks components of his enemy's network, that is, nodes and or/arcs; and in the second stage the enemy observes the damage caused by the attack and operates the damaged network so as to optimize a measure of functionality such as throughput, output or cost. For example, using a limited number of aerial sorties to attack and destroy production and distribution assets, an interdictor may wish to minimize the maximum “flow” of munitions that his enemy can produce and move to a battlefront. This article models interdictions with binary variables and simple constraints; solution of an optimization model, often a linear program, represents optimal network operation by the enemy. Simple models can be converted mixed‐integer programs, but solution methods based on decomposition may be preferred for efficiency and generality.

This publication has 49 references indexed in Scilit: