Partial-Enumeration for Planar Network Interdiction Problems
Abstract
In the network interdiction problem, an interdictor destroys a set of arcs in a capacitated network through which an adversary will maximize flow. The interdictor's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1998
- Accession Number
- ADA343529
Entities
People
- Michael R. Boyle
Organizations
- Naval Postgraduate School