Back to search

Clemson University

Network Interdiction under Uncertainty

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Industrial Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Holzmann, Timothy
Contributors dc:contributor
  • J C Smith, Committee Chair
  • Tugce Isik
  • Scott Mason
  • M G Sava
  • Margaret Wiecek

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2437

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Holzmann, Timothy. Network Interdiction under Uncertainty. Dissertation thesis, https://open.clemson.edu/all_dissertations/2437