Shortest-path network interdiction

Shortest-path network interdiction

0.00 Avg rating0 Votes
Article ID: iaor20032480
Country: United States
Volume: 40
Issue: 2
Start Page Number: 97
End Page Number: 111
Publication Date: Sep 2002
Journal: Networks
Authors: ,
Keywords: programming: integer
Abstract:

We study the problem of interdicting the arcs in a network 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 interdiction budget. We formulate this bilevel, max–min problem as mixed-integer program (MIP), which can be solved directly, but we develop more efficient decomposition algorithms. One algorithm enhances Benders decomposition 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.

Reviews

Required fields are marked *. Your email address will not be published.