A Lagrangian Heuristic for solving a network interdiction problem

Loading...
Thumbnail Image
Authors
Bingol, Levent
Subjects
Advisors
Wood, R. Kevin
Date of Issue
2001-12
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
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.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvii, 37 p. ;
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections