A Lagrangian Heuristic for solving a network interdiction problem
Wood, R. Kevin
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
A simulation tool for the duties of computer specialist non-commissioned officers on a Turkish Air Force Base Camur, Serhat. (Monterey, California. Naval Postgraduate School, 2009-09);Staff assignment is one of the major problems in many lines of business. Knowing that the human being is one of the most expensive and demanding resources, efficient personnel employing becomes significant. Simulation ...
Derbes, H. Dan (Monterey, California. Naval Postgraduate School, 1997-09);A network interdictor' has a limited supply of resource with which to disrupt a network user's" flow of supplies in a capacitated transshipment network. The interdictor's problem of minimizing the maximum flow through the ...
Gan, Eng Kiat Russell (Monterey, California. Naval Postgraduate School, 2012-09);This thesis describes three specialized branch-and-bound (B and B) algorithms for solving a mixed-integer program (MIP) that incorporates standard big-M constructs. The goal is to identify valid values for M that also lead ...