Date of Award
5-2022
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Industrial Engineering
Committee Chair/Advisor
Yongjia Song
Committee Member
J. Cole Smith
Committee Member
Mary Elizabeth Kurz
Committee Member
Brian C. Dean
Abstract
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 interests.
In the first problem, the leader acts first to lengthen a subset of arcs, and a follower acts second to select a shortest path across the network. The cost for a follower’s arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The leader is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The follower, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. We consider two variants of this problem. In the first variant, the leader is risk-neutral, whose goal is to maximize the expected minimum cost attainable by the follower. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen’s inequality as proposed in an earlier study on a maximum-flow interdiction problem. Several algorithmic strategies for accelerating the convergence of the algorithm are also introduced. In the second variant, the leader is risk-averse, seeking to maximize the conditional value-at-risk of the follower's shortest-path costs, given some specified risk parameter. We provide an exact method for this problem that utilizes row generation, partitioning, and bounding strategies. We demonstrate the efficacy of our approaches on randomly-generated instances.
In the second problem, the follower aims to access the sink node without being detected by the leader. Both players are aware of the probability of detection of each arc in the network. In the first stage, the leader interdicts and removes a subset of arcs from the network given a budget constraint. This information becomes available to the follower before the start of the second stage when both players participate in a simultaneous game. The simultaneous game involves the leader monitoring a subset of arcs to increase the probability of detecting the follower, and the follower traversing on a source-sink path. We present a tri-level formulation for the interdiction in a simultaneous game, as well as a bi-level reformulation that enables constraint and column generation and Benders decomposition to solve this problem exactly. We also provide strategies to improve the efficiency of the proposed solution approach along with computational results over a set of randomly-generated instances.
Recommended Citation
Nguyen, Di H., "Selected Interdiction Games with Uncertain, Risk-Averse, and Simultaneous Play Considerations" (2022). All Dissertations. 2974.
https://open.clemson.edu/all_dissertations/2974