A Lagrangian Heuristic for solving a network interdiction problem

Abstract

This thesis is concerned with solving or approximately solving a maximum-flow network-interdiction problem denoted MXFI: A network user strives to maximize flow of a commodity through a capacitated network, while an interdictor, with limited assets, attempts to destroy links in the network to minimize that maximum flow. MXFI can be converted to a binary integer program and solved but this approach can be computationally expensive. Earlier work by Derbes (1997) on a Lagrangian-relaxation technique has shown promise for solving the problem more quickly (Derbes, 1997). We extend his technique and implement algorithms in C to solve MXFI for all integer values of total interdiction resource available, R, in some specified range; interdictable arcs require one unit of resource to destroy. The basic procedure solves MXFI exactly for most values of R, but βproblematic valuesγ of R do arise. For one set of test problems, a heuristic handles these values successfully, with optimality gaps that are typically less than three percent. We test our algorithms and implementations using five test networks which range in size from 27 nodes and 86 arcs to 402 nodes and 1826 arcs. Using a 700 MHz Pentium III personal computer, we solve the largest problem in 16 seconds.