Network interdiction by Lagrangian relaxation and branch-and-bound

Loading...
Thumbnail Image
Authors
Uygun, Adnan
Subjects
Advisors
Wood, R. Kevin
Date of Issue
2002-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
The maximum-flow network-interdiction problem (MXFI) arises when an interdictor, using limited interdiction resources, wishes to restrict an adversary's use of a capacitated network. MXFI is not easy to solve when converted to a binary integer program. Derbes (1997) uses Lagrangian relaxation to solve the problem, at least approximately, for a single value of available resource, R. Bingol (2001) extends this technique to solve MXFI approximately for all integer values of R in a specified range. But, "problematic R-values" with substantial optimality gaps do arise. We reduce optimality gaps in two ways. First, we find the best Lagrangian multiplier for problematic R-values by following the slope of the Lagrangian function. Secondly, we apply a limited-enumeration branch-and-bound algorithm. We test our algorithms on six different test networks with up to 402 nodes and 1826 arcs. The algorithms are coded in Java 1.3 and run on a 533 MHz Pentium III computer. The first technique takes at most 39.3 seconds for any problem, and for one instance, it solves 8 of the problem's 15 problematic R-values. For that problem, the second technique solves four of the remaining problematic R-values, but run time increases by two orders of magnitude.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 47 p. : ill. ;
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