Prioritization and optimization in stochastic network interdiction problems

The goal of a network interdiction problem is to model competitive decision-making between two parties with opposing goals. The simplest interdiction problem is a bilevel model consisting of an 'adversary' and an interdictor. In this setting, the interdictor first expends resources to optimally disrupt the network operations of the adversary. The adversary subsequently optimizes in the residual interdicted network. In particular, this dissertation considers an interdiction problem in which the interdictor places radiation detectors on a transportation network in order to minimize the probability that a smuggler of nuclear material can avoid detection. A particular area of interest in stochastic network interdiction problems (SNIPs) is the application of so-called prioritized decision-making. The motivation for this framework is as follows: In many real-world settings, decisions must be made now under uncertain resource levels, e.g., interdiction budgets, available man-hours, or any other resource depending on the problem setting. Applying this idea to the stochastic network interdiction setting, the solution to the prioritized SNIP (PrSNIP) is a rank-ordered list of locations to interdict, ranked from highest to lowest importance. It is well known in the operations research literature that stochastic integer programs are among the most difficult optimization problems to solve. Even for modest levels of uncertainty, commercial integer programming solvers can have difficulty solving models such as PrSNIP. However, metaheuristic and large-scale mathematical programming algorithms are often effective in solving instances from this class of difficult optimization problems. The goal of this doctoral research is to investigate different methods for modeling and solving SNIPs (optimization) and PrSNIPs (prioritization via optimization). We develop a number of different prioritized and unprioritized models, as well as exact and heuristic algorithms for solving each problem type. The mathematical programming algorithms that we consider are based on row and column generation techniques, and our heuristic approach uses adaptive tabu search to quickly find near-optimal solutions. Finally, we develop a group of hybrid algorithms that combine various elements of both classes of algorithms.