Network Interdiction under Uncertainty.
Degree: PhD, Industrial Engineering, 2019, Clemson University
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.
Advisors/Committee Members: J C Smith, Committee Chair, Tugce Isik, Scott Mason, M G Sava, Margaret Wiecek.
Subjects/Keywords: Combinatorial Optimization; Industrial Engineering; Mathematical Programming; Multiobjective Optimization; Network Interdiction
to Zotero / EndNote / Reference
APA (6th Edition):
Holzmann, T. (2019). Network Interdiction under Uncertainty. (Doctoral Dissertation). Clemson University. Retrieved from https://tigerprints.clemson.edu/all_dissertations/2437
Chicago Manual of Style (16th Edition):
Holzmann, Timothy. “Network Interdiction under Uncertainty.” 2019. Doctoral Dissertation, Clemson University. Accessed September 21, 2019.
MLA Handbook (7th Edition):
Holzmann, Timothy. “Network Interdiction under Uncertainty.” 2019. Web. 21 Sep 2019.
Holzmann T. Network Interdiction under Uncertainty. [Internet] [Doctoral dissertation]. Clemson University; 2019. [cited 2019 Sep 21].
Available from: https://tigerprints.clemson.edu/all_dissertations/2437.
Council of Science Editors:
Holzmann T. Network Interdiction under Uncertainty. [Doctoral Dissertation]. Clemson University; 2019. Available from: https://tigerprints.clemson.edu/all_dissertations/2437