| Brown et al. (2004) (see also Reed 1994 and Skroch 2004) model the
completion of an adversarial nation’s nuclear-weapons program using
general techniques of PERT. (See PERT 1958 and Malcolm et al. 1959
for the original descriptions of PERT, and see Moder et al. 1983 for a
comprehensive review.) Brown et al. (2004) ask the question: How do
we most effectively employ limited interdiction resources, e.g., military
strikes or embargoes on key materials, to delay the project’s component
tasks, and thereby delay its overall completion time? They answer the
question by describing an interdiction model that maximizes minimum
project-completion time. This model is a Stackelberg game (von Stack-
elberg 1952), formulated as a bilevel integer-linear program (Moore and
Bard 1990).
Brown et al. (2004) consider a highly general model for project networks.
Specifically, they (i) allow the interdictor to employ various
interdiction resources, (ii) allow the project manager to “crash” the
project to speed project completion by applying various, constrained,
task-expediting resources, and (iii) allow the project manager to employ
alternative technologies to complete the project. The authors successfully
test an algorithm that solves a realistic example of the resulting
interdiction problem, but we shall see that the most general problem
is NP-hard. Thus, other large, general problems could be extremely
difficult to solve.
This paper therefore asks: How hard is the “project interdiction problem”
when full modeling generality is unnecessary? Can we assure analysts
that their version of the problem is not too difficult if modeling a
single interdiction resource suffices; or crashing is impossible; or only a
single technology, or modest number of technologies, need be modeled? |
