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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.