Academic literature on the topic 'Network interdiction problems'

Network interdiction problem arises when an unwanted agent attacks the network system to deteriorate its transshipment efficiency. Literature is flourished with models and solution approaches for the problem. This paper considers a single commodity lexicographic maximum flow problem on a directed network with capacitated vertices to study two network flow problems under an arc interdiction. In the first, the objective is to find an arc on input network to be destroyed so that the residual lexicographically maximum flow is lexicographically minimum. The second problem aims to find a flow pattern resulting lexicographically maximum flow on the input network so that the total residual flow, if an arc is destroyed, is maximum. The paper proposes strongly polynomial time solution procedures for these problems.

Goal recognition (GR) is a method of inferring the goals of other agents, which enables humans or AI agents to proactively make response plans. Goal recognition design (GRD) has been proposed to deliberately redesign the underlying environment to accelerate goal recognition. Along with the GR and GRD problems, in this paper, we start by introducing the goal recognition control (GRC) problem under network interdiction, which focuses on controlling the goal recognition process. When the observer attempts to facilitate the explainability of the actor’s behavior and accelerate goal recognition by reducing the uncertainty, the actor wants to minimize the privacy information leakage by manipulating the asymmetric information and delay the goal recognition process. Then, the GRC under network interdiction is formulated as one static Stackelberg game, where the observer obtains asymmetric information about the actor’s intended goal and proactively interdicts the edges of the network with a bounded resource. The privacy leakage of the actor’s actions about the real goals is quantified by a min-entropy information metric and this privacy information metric is associated with the goal uncertainty. Next in importance, we define the privacy information metric based GRC under network interdiction (InfoGRC) and the information metric based GRC under threshold network interdiction (InfoGRCT). After dual reformulating, the InfoGRC and InfoGRCT as bi-level mixed-integer programming problems, one Benders decomposition-based approach is adopted to optimize the observer’s optimal interdiction resource allocation and the actor’s cost-optimal path-planning. Finally, some experimental evaluations are conducted to demonstrate the effectiveness of the InfoGRC and InfoGRCT models in the task of controlling the goal recognition process.

Abstract Motivation Flux balance analysis (FBA) based bilevel optimization has been a great success in redesigning metabolic networks for biochemical overproduction. To date, many computational approaches have been developed to solve the resulting bilevel optimization problems. However, most of them are of limited use due to biased optimality principle, poor scalability with the size of metabolic networks, potential numeric issues or low quantity of design solutions in a single run. Results Here, we have employed a network interdiction model free of growth optimality assumptions, a special case of bilevel optimization, for computational strain design and have developed a hybrid Benders algorithm (HBA) that deals with complicating binary variables in the model, thereby achieving high efficiency without numeric issues in search of best design strategies. More importantly, HBA can list solutions that meet users’ production requirements during the search, making it possible to obtain numerous design strategies at a small runtime overhead (typically ∼1 h, e.g. studied in this article). Availability and implementation Source code implemented in the MATALAB Cobratoolbox is freely available at https://github.com/chang88ye/NIHBA. Contact math4neu@gmail.com or natalio.krasnogor@ncl.ac.uk Supplementary information Supplementary data are available at Bioinformatics online.

Most violent crimes happen in urban and suburban cities. With emerging tracking techniques, law enforcement officers can have real-time location information of the escaping criminals and dynamically adjust the security resource allocation to interdict them. Unfortunately, existing work on urban network security games largely ignores such information. This paper addresses this omission. First, we show that ignoring the real-time information can cause an arbitrarily large loss of efficiency. To mitigate this loss, we propose a novel NEtwork purSuiT game (NEST) model that captures the interaction between an escaping adversary and a defender with multiple resources and real-time information available. Second, solving NEST is proven to be NP-hard. Third, after transforming the non-convex program of solving NEST to a linear program, we propose our incremental strategy generation algorithm, including: (i) novel pruning techniques in our best response oracle; and (ii) novel techniques for mapping strategies between subgames and adding multiple best response strategies at one iteration to solve extremely large problems. Finally, extensive experiments show the effectiveness of our approach, which scales up to realistic problem sizes with hundreds of nodes on networks including the real network of Manhattan.

This study generalizes the r-interdiction median (RIM) problem with fortification to simultaneously consider two types of risks: probabilistic exogenous disruptions and endogenous disruptions caused by intentional attacks. We develop a bilevel programming model that includes a lower-level interdiction problem and a higher-level fortification problem to hedge against such risks. We then prove that the interdiction problem is supermodular and subsequently adopt the cuts associated with supermodularity to develop an efficient cutting-plane algorithm to achieve exact solutions. For the fortification problem, we adopt the logic-based Benders decomposition (LBBD) framework to take advantage of the two-level structure and the property that a facility should not be fortified if it is not attacked at the lower level. Numerical experiments show that the cutting-plane algorithm is more efficient than benchmark methods in the literature, especially when the problem size grows. Specifically, with regard to the solution quality, LBBD outperforms the greedy algorithm in the literature with an up-to 13.2% improvement in the total cost, and it is as good as or better than the tree-search implicit enumeration method. Summary of Contribution: This paper studies an r-interdiction median problem with fortification (RIMF) in a supply chain network that simultaneously considers two types of disruption risks: random disruptions that occur probabilistically and disruptions caused by intentional attacks. The problem is to determine the allocation of limited facility fortification resources to an existing network. It is modeled as a bilevel programming model combining a defender’s problem and an attacker’s problem, which generalizes the r-interdiction median problem with probabilistic fortification. This paper is suitable for IJOC in mainly two aspects: (1) The lower-level attacker’s interdiction problem is a challenging high-degree nonlinear model. In the literature, only a total enumeration method has been applied to solve a special case of this problem. By exploring the special structural property of the problem, namely, the supermodularity of the transportation cost function, we developed an exact cutting-plane method to solve the problem to its optimality. Extensive numerical studies were conducted. Hence, this paper fits in the intersection of operations research and computing. (2) We developed an efficient logic-based Benders decomposition algorithm to solve the higher-level defender’s fortification problem. Overall, this study generalizes several important problems in the literature, such as RIM, RIMF, and RIMF with probabilistic fortification (RIMF-p).

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.
Ph. D.

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

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.
Thesis Advisor(s): Wood, R. Kevin. "December 2001." Includes bibliographical references (p. 35-36). Also Available online.

Dans cette thèse, nous étudions le problème de l’Interdiction de l’Arbre Couvrant Minimal (IACM). Ce problème est un jeu à deux joueurs entre un opérateur de réseau et un interdicteur. Le premier détermine un Arbre Couvrant Minimal (ACM) dans un réseau. Limité par un budget, le second cherche à changer la topologie du réseau pour augmenter le poids de l’ACM. Deux types d’interdiction sont considérés : l’interdiction totale et l’interdiction partielle.Une arête totalement interdite est considérée comme absente tandis que le poids d’une arête partiellement interdite est augmentée d’une quantité prédéfinie. Le budget de l’interdicteur est modélisé par une contrainte de cardinalité,chaque arête a le même poids d’interdiction, ou une contrainte de sac `a dos, les poids d’interdiction peuvent être différents. Sept formulations mathématiques du problème IACM ont été élaborées. Elles se sont avérées efficaces pour des graphes de petite et moyenne taille. Un algorithme de type ”Branch-and-Price” et un algorithme basé sur la décomposition de Benders ont été conçus pour les graphes de plus grande taille. En outre, des inégalités valides sont proposées pour renforcer les modèles et améliorer les performances des algorithmes. Des instances de 200sommets et 19900 ar êtes ont ainsi pu être résolues optimalement
In this thesis, we study the Minimum Spanning Tree Interdiction (MSTI) problem. This problem is a two-player game between a network operator and an interdictor. The former aims to determine a Minimum Spanning Tree (MST) in a network. Constrained by a budget, the latter seeks to change the network topology to increase the weight of aMST. Two types of interdiction are considered: total and partial interdiction. A total interdicted edge is considered absent while the weight of a partial interdicted edge is augmented by a predefined amount. The interdictor’s budget ismodeled as a cardinality, each edge has the same interdiction weight, or knapsack constraint, the interdiction weightsmight be different. Seven mathematical formulations for the MSTI problem are devised. They proved to be efficient on small and medium-size graphs. A Branch-and-Price algorithm and a Benders Decomposition algorithm are designedfor larger graphs. In addition, valid inequalities are proposed to strengthen the models and improve the efficiency of the proposed methods. Instances including up to 200 nodes and 19900 edges are solved to optimality

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.

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

Preventing crimes or terrorist attacks in urban areas is challenging. Law enforcement officers need to respond quickly to catch the attacker on his escape route, which is subject to time-dependent traffic conditions on transportation networks. The attacker can strategically choose his escape path and driving speed to avoid being captured. Existing work on security resource allocation has not considered such scenarios with time-dependent strategies for both players. Therefore, in this paper, we study the problem of efficiently scheduling security resources for interdicting the escaping attacker. We propose: 1) a new defender-attacker security game model for escape interdiction on transportation networks; and 2) an efficient double oracle algorithm to compute the optimal defender strategy, which combines mixed-integer linear programming formulations for best response problems and effective approximation algorithms for improving the scalability of the algorithms. Experimental evaluation shows that our approach significantly outperforms baselines in solution quality and scales up to realistic-sized transportation networks with hundreds of intersections.

We study repeated network interdiction games with no prior knowledge of the adversary and the environment, which can model many real world network security domains. Existing works often require plenty of available information for the defender and neglect the frequent interactions between both players, which are unrealistic and impractical, and thus, are not suitable for our settings. As such, we provide the first defender strategy, that enjoys nice theoretical and practical performance guarantees, by applying the adversarial online learning approach. In particular, we model the repeated network interdiction game with no prior knowledge as an online linear optimization problem, for which a novel and efficient online learning algorithm, SBGA, is proposed, which exploits the unique semi-bandit feedback in network security domains. We prove that SBGA achieves sublinear regret against adaptive adversary, compared with both the best fixed strategy in hindsight and a near optimal adaptive strategy. Extensive experiments also show that SBGA significantly outperforms existing approaches with fast convergence rate.

Goal recognition, which is the task of inferring an agent’s goals given some or all of the agent’s observed actions, is one of the important approaches in bridging the gap between the observation and decision making within an observe-orient-decide-act cycle. Unfortunately, few researches focus on how to improve the utilization of knowledge produced by a goal recognition system. In this work, we propose a Markov Decision Process-based goal recognition approach tailored to a dynamic shortest-path local network interdiction (DSPLNI) problem. We first introduce a novel DSPLNI model and its solvable dual form so as to incorporate real-time knowledge acquired from goal recognition system. Then a Markov Decision Process-based goal recognition model along with its dynamic Bayesian network representation and the applied goal inference method is proposed to identify the evader’s real goal within the DSPLNI context. Based on that, we further propose an efficient scalable technique in maintaining action utility map used in fast goal inference, and develop a flexible resource assignment mechanism in DSPLNI using knowledge from goal recognition system. Experimental results show the effectiveness and accuracy of our methods both in goal recognition and dynamic network interdiction.