Academic literature on the topic 'Network interdiction problems'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Network interdiction problems.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Network interdiction problems"

1

Pavlikov, Konstantin. "Improved formulations for minimum connectivity network interdiction problems." Computers & Operations Research 97 (September 2018): 48–57. http://dx.doi.org/10.1016/j.cor.2018.04.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bhandari, Phanindra Prasad, and Shree Ram Khadka. "Lexicographically Maximum Flows under an Arc Interdiction." Journal of Nepal Mathematical Society 4, no. 2 (December 17, 2021): 8–14. http://dx.doi.org/10.3126/jnms.v4i2.41459.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

Luo, Junren, Xiang Ji, Wei Gao, Wanpeng Zhang, and Shaofei Chen. "Goal Recognition Control under Network Interdiction Using a Privacy Information Metric." Symmetry 11, no. 8 (August 17, 2019): 1059. http://dx.doi.org/10.3390/sym11081059.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Lim, Churlzu, and J. Cole Smith. "Algorithms for discrete and continuous multicommodity flow network interdiction problems." IIE Transactions 39, no. 1 (January 2007): 15–26. http://dx.doi.org/10.1080/07408170600729192.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jiang, Shouyong, Yong Wang, Marcus Kaiser, and Natalio Krasnogor. "NIHBA: a network interdiction approach for metabolic engineering design." Bioinformatics 36, no. 11 (March 13, 2020): 3482–92. http://dx.doi.org/10.1093/bioinformatics/btaa163.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

Malaviya, Ajay, Chase Rainwater, and Thomas Sharkey. "Multi-period network interdiction problems with applications to city-level drug enforcement." IIE Transactions 44, no. 5 (May 2012): 368–80. http://dx.doi.org/10.1080/0740817x.2011.602659.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Yates, Justin, Xinghua Wang, and Nannan Chen. "Assessing the effectiveness of k-shortest path sets in problems of network interdiction." Optimization and Engineering 15, no. 3 (May 31, 2013): 721–49. http://dx.doi.org/10.1007/s11081-013-9220-z.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Zhang, Youzhi, Qingyu Guo, Bo An, Long Tran-Thanh, and Nicholas R. Jennings. "Optimal Interdiction of Urban Criminals with the Aid of Real-Time Information." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1262–69. http://dx.doi.org/10.1609/aaai.v33i01.33011262.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Zhang, Kaike, Xueping Li, and Mingzhou Jin. "Efficient Solution Methods for a General r-Interdiction Median Problem with Fortification." INFORMS Journal on Computing 34, no. 2 (March 2022): 1272–90. http://dx.doi.org/10.1287/ijoc.2021.1111.

Full text
Abstract:
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).
APA, Harvard, Vancouver, ISO, and other styles
10

Yates, Justin, and Sujeevraja Sanjeevi. "A length-based, multiple-resource formulation for shortest path network interdiction problems in the transportation sector." International Journal of Critical Infrastructure Protection 6, no. 2 (June 2013): 107–19. http://dx.doi.org/10.1016/j.ijcip.2013.04.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Network interdiction problems"

1

Boyle, Michael R. "Partial-enumeration for planar network interdiction problems." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1998. http://handle.dtic.mil/100.2/ADA343529.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Cormican, Kelly James. "Computational methods for deterministic and stochastic network interdiction problems." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1995. http://handle.dtic.mil/100.2/ADA297596.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Lunday, Brian Joseph. "Resource Allocation on Networks: Nested Event Tree Optimization, Network Interdiction, and Game Theoretic Methods." Diss., Virginia Tech, 2010. http://hdl.handle.net/10919/77323.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Altner, Douglas S. "Advancements on problems involving maximum flows." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24828.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

Akgun, Ibrahim. "The K-group maximum-flow network-interdiction problem." Thesis, Monterey, California. Naval Postgraduate School, 2000. http://hdl.handle.net/10945/32947.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

Bingol, Levent. "A Lagrangian Heuristic for solving a network interdiction problem." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2001. http://handle.dtic.mil/100.2/ADA401595.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
7

Salazar, zendeja Luis. "Modèles et algorithmes pour le problème d'interdiction de l'arbre couvrant de poids minimal." Electronic Thesis or Diss., Centrale Lille Institut, 2022. http://www.theses.fr/2022CLIL0028.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
8

Cabalka, Matouš. "Pokročilá optimalizace toků v sítích." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2018. http://www.nusl.cz/ntk/nusl-392835.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Michalopoulos, Dennis Paul 1979. "Prioritization and optimization in stochastic network interdiction problems." 2008. http://hdl.handle.net/2152/18188.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
10

Nehme, Michael Victor. "Two-person games for stochastic network interdiction : models, methods, and complexities." 2009. http://hdl.handle.net/2152/7512.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Network interdiction problems"

1

Smith, J. Cole, Mike Prince, and Joseph Geunes. "Modern Network Interdiction Problems and Algorithms." In Handbook of Combinatorial Optimization, 1949–87. New York, NY: Springer New York, 2013. http://dx.doi.org/10.1007/978-1-4419-7997-1_61.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Torres, Marina, Shouyong Jiang, David Pelta, Marcus Kaiser, and Natalio Krasnogor. "Strain Design as Multiobjective Network Interdiction Problem: A Preliminary Approach." In Advances in Artificial Intelligence, 273–82. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-00374-6_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Schäfer, Luca E., Tobias Dietz, Marco V. Natale, Stefan Ruzika, Sven O. Krumke, and Carlos M. Fonseca. "The Bicriterion Maximum Flow Network Interdiction Problem in s-t-Planar Graphs." In Operations Research Proceedings, 133–39. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-48439-2_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Khanduzi, Raheleh, and Abdolmotalleb Rastegar. "Designing a cooperative hierarchical model of interdiction median problem with protection and its solution approach: A case study of health-care network." In Intelligent IoT Systems in Personalized Health Care, 53–88. Elsevier, 2021. http://dx.doi.org/10.1016/b978-0-12-821187-8.00003-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Network interdiction problems"

1

Zhang, Youzhi, Bo An, Long Tran-Thanh, Zhen Wang, Jiarui Gan, and Nicholas R. Jennings. "Optimal Escape Interdiction on Transportation Networks." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/550.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
2

Matta, Krish, Xiaoyuan Liu, and Ilya Safro. "Decomposition Based Refinement for the Network Interdiction Problem." In 2023 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 2023. http://dx.doi.org/10.1109/hpec58863.2023.10363524.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Guo, Qingyu, Bo An, and Long Tran-Thanh. "Playing Repeated Network Interdiction Games with Semi-Bandit Feedback." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/515.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Janjarassuk, U., and T. Nakrachata-Amon. "A simulated annealing algorithm to the stochastic network interdiction problem." In 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2015. http://dx.doi.org/10.1109/ieem.2015.7385642.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Xu, Kai, Kaiming Xiao, Quanjun Yin, Yabing Zha, and Cheng Zhu. "Bridging the Gap between Observation and Decision Making: Goal Recognition and Flexible Resource Allocation in Dynamic Network Interdiction." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/625.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

Kuhnle, Alan, Victoria G. Crawford, and My T. Thai. "Scalable and Adaptive Algorithms for the Triangle Interdiction Problem on Billion-Scale Networks." In 2017 IEEE International Conference on Data Mining (ICDM). IEEE, 2017. http://dx.doi.org/10.1109/icdm.2017.33.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Network interdiction problems"

1

Chauhan, Darshan Rajesh. Robust Maximum Flow Network Interdiction Problem. Portland State University Library, January 2020. http://dx.doi.org/10.15760/etd.7315.

Full text
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography