Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"interdiction problems"”.
-
Partial-enumeration for planar network interdiction problems
In the network interdiction problem, an interdictor destroys a set of arcs in a capacitated network through which an adversary will maximize flow. The interdictor's primary objective is to use his limited resources to minimize that maximum flow, but other objectives may be important. Therefore, we …
-
Combinatorial Relaxations and Algorithms for Interdiction Problems
In an interdiction problem, there are two players, the leader and the follower. The follower aims to solve some combinatorial optimization problem, such as knapsack, maximum matching, or shortest path. However, the leader, who acts before the follower, is able to pay some cost to destroy (i.e., …
-
OPTIMISATION AND INTERDICTION PROBLEMS FOR NETWORK SAFETY
In this thesis, we explore optimisation problems related to security, focusing on real-world systems that can be modelled using graphs or binary matrices. The first problem we examine is the Weighted Safe Set Problem, a graph optimisation problem that seeks to identify vertex partitions satisfying …
-
Prioritization and optimization in stochastic network interdiction problems
The goal of a network interdiction problem is to model competitive decision-making between two parties with opposing goals. The simplest interdiction problem is a bilevel model consisting of an 'adversary' and an interdictor. In this setting, the interdictor first expends resources to optimally …
-
Computational methods for deterministic and stochastic network interdiction problems
… algorithm is utilized to investigate cases where interdiction successes are binary random variables. For a network of 3200 nodes and 6280 arcs, Benders decomposition solves the network interdiction problem in less than one-third of the time required by a direct branch-and-bound method. The …
-
Distributionally robust solution schemes for two-stage optimization and interdiction problems under uncertainty
… uncertain parameters to formulate the decision problems. Despite its wide applications in real-world problems, optimization under uncertainty gives rise to computational challenges. This thesis aims to design tractable solution schemes with performance guarantees for two-stage optimization and …
-
Algorithms for Distributionally Risk-Receptive and Robust Stochastic Integer Programs and Interdiction Problems
… with a particular focus on adversarial games and interdiction problems. We introduce models within both distributionally risk-receptive (DRR) and distributionally robust optimization (DRO) frameworks, allowing for an adjustment of decision-maker's risk attitudes in adversarial settings. A key …
-
RUNTIME ANALYSIS OF BENDERS DECOMPOSITION AND DUAL ILP ALGORITHMS AS APPLIED TO COMMON NETWORK INTERDICTION PROBLEMS
… network. This thesis analyzes two network interdiction algorithms, Benders decomposition and a dual integer linear program approach, to compare their computational efficiency on the shortest path and maximum flow interdiction problems. We construct networks using two operationally …
-
System interdiction and defense
… developed and illustrated with a simple network interdiction problem, "maximizing the shortest path" (MXSP). In MXSP, an interdictor wishes to employ limited interdiction resources as effectively as possible to slow an adversary in moving between two network nodes. "Interdiction" destroys a …
-
Stream sketches, sampling, and sabotage
Exact solutions are unattainable for important problems. The calculations are limited by the memory of our computers and the length of time that we can wait for a solution. The field of approximation algorithms has grown to address this problem; it is practically important and theoretically …
-
Stochastic network interdiction games
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 …
-
Interdicting electrical power grids
… explores Benders decomposition for solving interdiction problems on electric power grids, with applications to analyzing the vulnerability of such grids to terrorist attacks. We refine and extend some existing optimization models and algorithms and demonstrate the value of our techniques …
-
BOUNDARY SEARCH AND TRAVERSE: DETERMINING THE THRESHOLD BOUNDARY FOR INFRASTRUCTURE NETWORK RESILIENCE PROBLEMS
Traditional network interdiction problems focus on finding the target package that yields the worst-case performance for network operations given a level of attack. However, in many cases it may be desirable to disrupt a network such that its performance falls below a given performance threshold …
-
Efficiently interdicting a time-expanded transshipment network
… (without considering time) and dynamic network interdiction problems. Static test networks range in size from 25 nodes and 64 arcs to 400 nodes and 1519 arcs. Using an IBM Rs/6000 Model 590 workstation, we find optimal solutions for seven of 12 test networks and solve the largest problem in only …
-
Bilevel Network Interdiction Models for Human Trafficking Disruption
… we study a series of bilevel network interdiction problems motivated by applications in human trafficking disruption. First, we consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node and the leader …
-
Integer Programming Methods for Boolean Interdiction Games
Interdiction games are commonly used to model scenarios where two actors with conflicting objectives both aim to operate optimally. We define an abstract game called the Boolean interdiction that captures the essence of an important subclass of these interdiction games. Then, we use an application, …
-
Stochastic network interdiction: models and methods
We develop stochastic network interdiction models and associated solution methods. In its simplest form, our model consists of a smuggler who wishes to traverse a network from an origin to a destination without being detected. Probabilities associated with the indigenous transportation network …
-
Exact Algorithms for Mixed-Integer Multilevel Programming Problems
We examine multistage optimization problems, in which one or more decision makers solve a sequence of interdependent optimization problems. In each stage the corresponding decision maker determines values for a set of variables, which in turn parameterizes the subsequent problem by modifying its …
-
Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations.
… 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 …
-
Selected Interdiction Games with Uncertain, Risk-Averse, and Simultaneous Play Considerations
This dissertation examines two network interdiction problems: a shortest-path interdiction problem under uncertainty and a network interdiction problem in a simultaneous game. Both problems happen in two stages over a directed network, and involve a leader and a follower who have opposing …
Page 1 of 2