<div class="description">
<p>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.
</p>
<br>Subjects: Lagrangian functions; Computer networks</div>
<div class="fn value">
Uygun, Adnan</div>
Internet Archive identifier