Dissertations / Theses on the topic 'Interdiction networks'

Approved for public release; distribution is unlimited<br>To interdict dark networks and prevent terrorist attacks, security forces require consistent access to relevant intelligence and targeting data. Dark networks often react to a security force’s targeting pressure by obscuring their activities and becoming increasingly covert. Network adaptation to targeting pressure can frequently lead to intelligence gaps and lulls in targeting that may be both predictable and preventable if identified early. This study will examine the efficacy of the two prevailing modes of targeting and their impact on resilient dark networks. To achieve this goal, this thesis will conduct a multivariate path analysis using temporal, geospatial, and relational data of a select dark network as these two modes of intelligence collection and targeting are employed against the network over time. By achieving this goal, this thesis will generate policy recommendations for operationalizing the outcomes of this study in order to better formulate how the prevailing modes of targeting can more effectively be implemented to address adaptive terrorist threats.

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry.<br>Ph. D.

Thesis (M.S. in Information Technology Management)--Naval Postgraduate School, September 2006.<br>Thesis Advisor(s): Alex Bordetsky. "September 2006." Includes bibliographical references (p. 79-81). Also available in print.

Robust communications are key to the success of naval operations such as area surveillance, control, and interdiction. Communication and sensor networks allow the flow of data and critical information that is necessary for conducting an operation from both the tactical and strategic perspectives. In naval operations, the platforms are hardly stationary, as the networking infrastructure operates from a variety of platforms in motion on the sea, above the sea, and from space, in the case of satellite support. Sensor networks consist of nodes made up of small sensors that are able to monitor, process, and analyze phenomena over geographical regions of varying sizes and for significant periods. Some categories of these small, and sometimes low-cost, sensors are able to collect and transmit, or relay, sensor data about physical values (e.g., temperature, humidity, and sea state), or dynamic attributes of objects, such as speed, direction, and the existence of dangerous substances (e.g., radioactive materials and explosives). The objective of this thesis is to examine how unstructured sensor networks, known also as ad-hoc sensor networks, can effectively support maritime interdiction operations and regional security by providing reliable communications and flow of information.

Network Interdiction-problem innehåller två mot varandra stående styrkor, en användare och en angripare, somär inbegripna i en krigsliknande konflikt. Användaren använder ett nätverk för att optimera en funktion, t.ex.att förflytta en underhållskonvoj så snabbt som möjligt, eller maximera mängden materiel som transporterasgenom nätverket. Det innebär att användaren vill använda den kortaste eller snabbaste vägen vid transporter,och han vill maximera flödet genom nätverket. Nätverket kan t.ex. vara ett vägnät, kraftförsörjningsnät eller ettdatornätverk. Angriparen försöker begränsa användarens möjlighet att optimera sin funktion. Angriparenssyftet är att maximera den kortaste/snabbaste vägen eller att minimera det maximala flödet genom nätverket.Angriparen uppnår detta genom att angripa bågar eller noder i nätverket och förstöra dem totalt eller reduceraderas kapacitet. Angriparens resurser är begränsade och det finns ett behov av att optimera användandet. Imånga fall är nätverket stort och många parametrar påverkar planeringen. Detta ger en komplexplaneringsförutsättning för angriparen. Genomförs planläggningen av Network Interdiction på traditionellt sätt,tvingas planeraren att använda sin intuition. Resultatet beror till stor del på planläggarens förmåga och tid tillförfogande. Om algoritmer kunde användas för att stödja planläggaren, skulle resursutnyttjandet och effektenav angreppen kunna optimeras. Uppsatsen undersöker om det är möjligt att använda Network Interdictionalgoritmervid planering av Network Interdiction.<br>Network interdiction problems involve two opposing forces, a user and anattacker, who are engaged in a warlike conflict. The user operates a network inorder to optimize a function such as moving a supply convoy through thenetwork as quickly as possible, or maximizing the amount of materieltransported through the network. This means that the user is trying to use theshortest or the fastest route to perform transports, and he is trying to maximizethe flow trough the network. The network could be a road net, an electric powergrid or a computer network system. The attacker attempts to limit the user’spossibility to optimize his function. The purpose is to maximize the shortest andfastest route or to minimize the maximum flow through the network. Theattacker obtains this by interdicting arcs or nodes, e.g. by attacking arcs or nodesin order to destroy them entirely or to reduce their capacity. The attacker’sresources are limited and there is a need to optimize the use of them. In manycases the network is big and numerous parameters influence the planning. Thismakes the conditions for planning complex and difficult for the attacker. If theplanning of network interdiction is performed in the traditional way, the planneris forced to use intuition. The result will depend on the planner’s capacity and thetime at his disposal. If algorithms could be used to support the planner, theresources and the effect of the attack would be optimized. This thesis examines ifit is possible to use network interdiction algorithms to plan network interdiction.<br>Avdelning: ALB - Slutet Mag 3 C-upps.Hylla: Upps. ChP T 01-03

Thesis (Ph.D.)--Boston University<br>Network interdiction problems consist of games between an attacker and an intelligent network, where the attacker seeks to degrade network operations while the network adapts its operations to counteract the effects of the attacker. This problem has received significant attention in recent years due to its relevance to military problems and network security. When the attacker's actions achieve uncertain effects, the resulting problems become stochastic network interdiction problems. In this thesis, we develop new algorithms for the solutions of different classes of stochastic network interdiction problems. We first focus on static network interdiction games where the attacker attacks the network once, which will change the network with certain probability. Then the network will maximize the flow from a given source to its destination. The attacker is seeking a strategy which minimizes the expected maximum flow after the attack. For this problem, we develop a new solution algorithm, based on parsimonious integration of branch and bound techniques with increasingly accurate lower bounds. Our method obtains solutions significantly faster than previous approaches in the literature. In the second part, we study a multi-stage interdiction problem where the attacker can attack the network multiple times, and observe the outcomes of its past attacks before selecting a current attack. For this dynamic interdiction game, we use a model-predictive approach based on a lower bound approximation. We develop a new set of performance bounds, which are integrated into a modified branch and bound procedure that extends the single stage approach to multiple stages. We show that our new algorithm is faster than other available methods with simulated experiments. In the last part, we study the nested information game between an intelligent network and an attacker, where the attacker has partial information about the network state, which refers to the availability of arcs. The attacker does not know the exact state, but has a probability distribution over the possible network states. The attacker makes several attempts to attack the network and observes the flows on the network. These observations will update the attacker's knowledge of the network and will be used in selecting the next attack actions. The defender can either send flow on that arc if it survived, or refrain from using it in order to deceive the attacker. For these problems, we develop a faster algorithm, which decomposes this game into a sequence of subgames and solves them to get the equilibrium strategy for the original game. Numerical results show that our method can handle large problems which other available methods fail to solve.

We study the K-group network-interdiction problem (KNIP) in which a "network user" attempts to maximize flow among K >/= 3 "node groups", while an "interdictor" interdicts (destroys) network arcs, using limited interdiction resources, to minimize this maximum flow. We develop two models to solve or approximately solve KNIP. The multi-partition network-interdiction model (MPNIM) is an approximating model. It partitions the node set N into K different subsets, each containing one prespecified node group, and interdicts arcs using limited resources so that the total capacity of uninterdicted arcs crossing between subsets is minimized. The multi-commodity network-interdiction model (MCNIM) explicitly minimizes the maximum amount of flow that can potentially be moved among node groups using K single-commodity flow models connected by joint capacity constraints. It is a min-max model but is converted into an equivalent integer program MCNIM-IP. Both MPNIM and MCNIM-IP are tested using four artificially constructed networks with up to 126 nodes, 333 arcs, K = 5, and 20 interdictions allowed. Using a 333 MHz Pentium II personal computer, maximum solution times are 563.1 seconds for MPNIM but six of 16 MCNIM-IP problems cannot be solved in under 3,600 seconds.

Thesis (M.S. in Operations Research) Naval Postgraduate School, December 2001.<br>Thesis Advisor(s): Wood, R. Kevin. "December 2001." Includes bibliographical references (p. 35-36). Also Available online.

In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as , the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and , the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget is related to all of these parameters of the network. Additionally, we present formulations to estimate both and . For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.

This thesis describes a stochastic, network interdiction optimization model to guide defensive, counter-air (DCA) operations planning. We model a layered, integrated air-defense system, which consists of fighter and missile engagement zones. We extend an existing two-stage, stochastic, generalized-network interdiction model by Pan, Charlton and Morton, and adapt it to DCA operations planning. The extension allows us to handle multiple-type interdiction assets, and constrain the attacker's flight path by the maximum allowable traveled distance. The defender selects the locations to install multiple interceptor types, with uncertainty in the attacker's origin and destination, in order to minimize the probability of evasion, or the expected target value collected by the evader. Then, the attacker reveals an origin-destination pair (independent of the defender's decision), and sends a strike package along a path (through the interdicted network) that maximizes his probability of evasion. By adding a small persistence penalty we ensure the plans are consistent in presence of minor variations in the number of interceptors. We present computational results for several instances of a test case consisting of the airspace over a 360-by-360 nautical miles area. The computational time ranges from some seconds to ten minutes, which is acceptable for operational use of this model.

Thesis (M.S. in Operations Research) Naval Postgraduate School, September 1997.<br>"September 1997." Thesis advisor(s): R. Kevin Wood. Includes bibliographical references (p. 67-68). Also available online.

Thesis (M.S. in Operations Research)--Naval Postgraduate School, June 2010.<br>Thesis Advisor(s): Wood, R. Kevin ; Second Reader: Salmeron, Javier. "June 2010." Description based on title screen as viewed on July 14, 2010. Author(s) subject terms: Two-person zero-sum network-interdiction game, game theoretic network interdiction, column generation, pure inspection-assignment strategy, inspector-to-edge assignment and mixed strategies, marginal probability, Cournet's simultaneous play game. Includes bibliographical references (p. 47-48). Also available in print.

Approved for public release; distribution is unlimited<br>This research intends to improve information dominance in the maritime domain by optimizing tactical mobile ad hoc network (MANET) systems for wireless sharing of biometric data in maritime interdiction operations (MIO). Current methods for sharing biometric data in MIO are unnecessarily slow and do not leverage wireless networks at the tactical edge to maximize information dominance. Field experiments allow students to test wireless MANETs at the tactical edge. Analysis is focused on determining optimal MANET design and implementation. It considers various implementations with varied antenna selection, radio power, and frequency specifications, and two specific methods of integrating Department of Defense biometric collection devices to the wireless MANET, which utilizes a single (WR) MPU4 802.11 Wi-Fi access point to connect secure electronic enrollment kit II (SEEK II) biometric devices to the MANET, and tethers each SEEK device to a dedicated WR using a personal Ethernet connection. Biometric data is shared across the tactical network and transmitted to remote servers. Observations and analysis regarding network performance demonstrate that wireless MANETs can be optimized for biometric reach back and integrated with biometric devices to improve biometric data sharing in MIO.

Thesis (M.S. in Information Technology Management)--Naval Postgraduate School, September 2009.<br>Thesis Advisor(s): Ehlert, James ; Barreto, Albert. "September 2009." Description based on title screen as viewed on November 5, 2009. Author(s) subject terms: MIO, VBSS, electronically steered antenna, phased array antenna, wireless network connection, Wi-Fi, IEEE 802.11g, boarding team, COTS, WLAN, smart antenna, OpenVPN application, wireless base station, OFDM, latency, point-to-point wireless link. Includes bibliographical references (p. 81-82). Also available in print.

Thesis (Ph.D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2008.<br>Committee Chair: Ozlem Ergun; Committee Member: Dana Randall; Committee Member: Joel Sokol; Committee Member: Shabbir Ahmed; Committee Member: William Cook.

In this dissertation we focus on two main topics. Under the first topic, we develop a new framework for stochastic network interdiction problem to address ambiguity in the defender risk preferences. The second topic is dedicated to computational studies of two-stage stochastic integer programs. More specifically, we consider two cases. First, we develop some solution methods for two-stage stochastic integer programs with continuous recourse; second, we study some computational strategies for two-stage stochastic integer programs with integer recourse. We study a class of stochastic network interdiction problems where the defender has incomplete (ambiguous) preferences. Specifically, we focus on the shortest path network interdiction modeled as a Stackelberg game, where the defender (leader) makes an interdiction decision first, then the attacker (follower) selects a shortest path after the observation of random arc costs and interdiction effects in the network. We take a decision-analytic perspective in addressing probabilistic risk over network parameters, assuming that the defender's risk preferences over exogenously given probabilities can be summarized by the expected utility theory. Although the exact form of the utility function is ambiguous to the defender, we assume that a set of historical data on some pairwise comparisons made by the defender is available, which can be used to restrict the shape of the utility function. We use two different approaches to tackle this problem. The first approach conducts utility estimation and optimization separately, by first finding the best fit for a piecewise linear concave utility function according to the available data, and then optimizing the expected utility. The second approach integrates utility estimation and optimization, by modeling the utility ambiguity under a robust optimization framework following \cite{armbruster2015decision} and \cite{Hu}. We conduct extensive computational experiments to evaluate the performances of these approaches on the stochastic shortest path network interdiction problem. In third chapter, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches. In chapter four, we concentrate on computational methods for two-stage stochastic integer program with integer recourse. We consider the partition-based relaxation framework integrated with a scenario decomposition algorithm in order to develop strategies which provide a better lower bound on the optimal objective value, within a tight time limit.

The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.

We analyze an interdiction problem in which a nuclear-material smuggler can traverse multiple transportation networks, wherein each edge has an indigenous probability of evasion. Our objective is to determine the optimal locations of a limited number of radiation detectors at United States ports of entry across multiple networks (maritime, road and rail) so as to minimize the smuggler's total probability of evasion, from origin to destination. We choose geographically diverse potential origins and give the smuggler freedom to move across and between transportation networks. Further, we consider two different models of smuggler behavior in this context. Our analysis aims to provide a complete prioritization and picture of the threat at all ports of entry, leading to insight into good practical locations for detectors.<br>text

We analyze an interdiction problem in which a nuclear-material smuggler can traverse the rail and road ports of entry (POEs) along the Mexican and Canadian borders of the United States. Our objective is to determine the optimal locations of a limited number of transparent and non-transparent assets so as to minimize the smuggler’s total probability of evasion, from origin to destination. We choose origins in Mexico and Canada and give the smuggler a diverse set of destinations to choose from. Our analysis aims to provide a complete prioritization and picture of the threat at Mexican and Canadian POEs, leading to insight into practical locations for transparent and non-transparent assets.<br>text

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

We describe a stochastic network interdiction problem in which an interdictor, subject to limited resources, installs radiation detectors at border checkpoints in a transportation network in order to minimize the probability that a smuggler of nuclear material can traverse the residual network undetected. The problems are stochastic because the smuggler's origin-destination pair, the mass and type of material being smuggled, and the level of shielding are known only through a probability distribution when the detectors are installed. We consider three variants of the problem. The first is a Stackelberg game which assumes that the smuggler chooses a maximum-reliability path through the network with full knowledge of detector locations. The second is a Cournot game in which the interdictor and the smuggler act simultaneously. The third is a "hybrid" game in which only a subset of detector locations is revealed to the smuggler. In the Stackelberg setting, the problem is NP-complete even if the interdictor can only install detectors at border checkpoints of a single country. However, we can compute wait-and-see bounds in polynomial time if the interdictor can only install detectors at border checkpoints of the origin and destination countries. We describe mixed-integer programming formulations and customized branch-and-bound algorithms which exploit this fact, and provide computational results which show that these specialized approaches are substantially faster than more straightforward integer-programming implementations. We also present some special properties of the single-country case and a complexity landscape for this family of problems. The Cournot variant of the problem is potentially challenging as the interdictor must place a probability distribution over an exponentially-sized set of feasible detector deployments. We use the equivalence of optimization and separation to show that the problem is polynomially solvable in the single-country case if the detectors have unit installation costs. We present a row-generation algorithm and a version of the weighted majority algorithm to solve such instances. We use an exact-penalty result to formulate a model in which some detectors are visible to the smuggler and others are not. This may be appropriate to model "decoy" detectors and detector upgrades.<br>text