Partial-Enumeration for Planar Network Interdiction Problems
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
In the network interdiction problem, an interdictor destroys a set of arcs in a capacitated network through which an adversary will maximize flow. The interdictors primary objective is to use his limited resources to minimize that maximum flow, but other objectives may be important. Therefore, we describe algorithms for enumerating near optimal interdiction sets in planar networks so that these sets may be evaluated with respect to secondary criteria, e.g., safety of attacking forces, collateral damage, etc. Our algorithms are based on enumerating near shortest paths or cycles in the dual of a planar network they find a single optimum interdiction set in pseudo polynomial time. We implement one algorithm applicable to s-t planar networks s and t must lie on the perimeter of the network and solve problems with up to 800 nodes and 1247 arcs. An example of computational results on that largest network is The algorithm enumerates all 19 solutions that are within 50 of optimal in 0.15 seconds on a 300 MHz Pentium 2 PC. We also propose, but do not implement, a somewhat less efficient extension of this algorithm to solve problems on general planar networks.
- Operations Research
- Military Operations, Strategy and Tactics