Date of Award
8-2019
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Industrial Engineering
Committee Member
J C Smith, Committee Chair
Committee Member
Tugce Isik
Committee Member
Scott Mason
Committee Member
M G Sava
Committee Member
Margaret Wiecek
Abstract
We consider variants to one of the most common network interdiction formulations: the shortest path interdiction problem. This problem involves leader and a follower playing a zero-sum game over a directed network. The leader interdicts a set of arcs, and arc costs increase each time they are interdicted. The follower observes the leader's actions and selects a shortest path in response. The leader's optimal interdiction strategy maximizes the follower's minimum-cost path.
Our first variant allows the follower to improve the network after the interdiction by lowering the costs of some arcs, and the leader is uncertain regarding the follower's cardinality budget restricting the arc improvements. We propose a multiobjective approach for this problem, with each objective corresponding to a different possible improvement budget value. To this end, we also present the modified augmented weighted Tchebychev norm, which can be used to generate a complete efficient set of solutions to a discrete multi-objective optimization problem, and which tends to scale better than competing methods as the number of objectives grows.
In our second variant, the leader selects a policy of randomized interdiction actions, and the follower uses the probability of where interdictions are deployed on the network to select a path having the minimum expected cost. We show that this continuous non-convex problem becomes strongly NP-hard when the cost functions are convex or when they are concave. After formally describing each variant, we present various algorithms for solving them, and we examine the efficacy of all our algorithms on test beds of randomly generated instances.
Recommended Citation
Holzmann, Timothy, "Network Interdiction under Uncertainty" (2019). All Dissertations. 2437.
https://tigerprints.clemson.edu/all_dissertations/2437