Accession Number:

ADA343529

Title:

Partial-Enumeration for Planar Network Interdiction Problems

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

• Boyle, Michael R.

Report Date:

1998-03-01

Pagination or Media Count:

56.0

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 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.

Descriptors:

• *ALGORITHMS
• *INTERDICTION
• *MILITARY TACTICS
• COMPUTERIZED SIMULATION
• MILITARY SUPPLIES
• MILITARY STRATEGY
• THESES
• STRATEGIC WARFARE
• COMMODITIES
• NETWORK FLOWS

Subject Categories:

• Operations Research
• Military Operations, Strategy and Tactics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE