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.
RightsThis 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.
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 ...
RUNTIME ANALYSIS OF BENDERS DECOMPOSITION AND DUAL ILP ALGORITHMS AS APPLIED TO COMMON NETWORK INTERDICTION PROBLEMS Trask, Timothy S., Jr. (Monterey, CA; Naval Postgraduate School, 2022-06);Attacker-defender models help practitioners understand a network’s resistance to attack. An assailant interdicts a network, and the operator responds in such a way as to optimally utilize the degraded network. This thesis ...
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 ...