Network Interdiction by Lagrandian Relaxation and Branch-and-Bound
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
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2002
- Accession Number
- ADA406059
Entities
People
- Adnan Uygun
Organizations
- Naval Postgraduate School