Shortest‐Path Network Interdiction

Abstract

We study the problem of interdicting the arcs in a net- work in order to maximize the shortest s–t path length. “Interdiction” is an attack on an arc that destroys the arc or increases its effective length; there is a limited inter- diction budget. We formulate this bilevel, max–min prob- lem as a mixed-integer program (MIP), which can be solved directly, but we develop more efficient decompo- sition algorithms. One algorithm enhances Benders de- composition by adding generalized integer cutting planes, called “supervalid inequalities” (SVIs), to the master problem. A second algorithm exploits a unique set-covering master problem. Computational results demonstrate orders-of-magnitude improvements of the decomposition algorithms over direct solution of the MIP and show that SVIs also help solve the original MIP faster.