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