Decision support for deterministic network interdiction operations

Emily Seah Xiang Ru

Abstract

Network interdiction is commonly used to describe network flow problems where an opponent, constrained by a limited resource, is required to disrupt the enemy's traversal across the network. The first part of my thesis extends the formulations of Kevin Wood's 1993 min-max flow model to node-arc interdictions and multi-period interdictions. However, Wood's model failed to capture resource wastage in redundant interdictions. Part two of my thesis develops an iterative algorithm to address this limitation. We achieve Pareto optimality by optimizing a lexicographic dual objective function which first minimizes max flow and next minimizes resource wastage. Subsequently, an "anytime algorithm" is developed to construct an efficiency frontier. This efficiency frontier allows the interdictor to manage tradeoffs between resource usage and interdiction outcomes. With rising concerns in resource usage efficiencies, a "just-enough" interdiction problem is introduced and formulated in part three of this thesis. In that problem, we minimize resources used to ensure enemy's shortest path through the network is at least a tolerable value T. ILOG's OPL Studio 3.7 will be used to solve the relevant integer programs.