Yang, Jing
(2022)
Essays on Interdiction Problems in Novel Settings.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
We study bilevel optimization problems that model decentralized decision-making settings with two independent decision-makers (DMs), who act in a hierarchical manner. These DMs are referred to as a leader and a follower. The leader acts first and then the follower solves its own optimization problem, which depends on the leader’s decision. Our focus is on interdiction problems that are motivated by defense and security related applications, where the DMs are also known as an interdictor and an evader, or an attacker/defender and a defender/attacker, respectively.
This dissertation consists of three essays on interdiction problems in novel settings. In the first essay, we study bilevel programs, where a fractional objective function appears in the follower’s problem. These programs generalize standard bilevel linear mixed-integer programs with a linear program in the lower level. Our work is motivated by an interdiction setting, where the evader optimizes some efficiency-based objective, e.g., a cost-to-time ratio. The proposed solution approach relies on a reformulation that can be solved with off-the-shelf solvers.
We then study sequential network interdiction problems, where the interdictor and the evader interact over multiple time periods. In each period the interdictor with incomplete knowledge of the network blocks a subset of arcs, and then the evader with complete knowledge traverses via a path between two fixed nodes. In the second and the third essays we consider two different novel settings, where we make different assumptions on the evader’s decision-making process and on the information feedback (from the evader’s actions) to the interdictor. Specifically, in the second essay, we assume that the evader solves the shortest path problem and the interdictor observes only the total cost of the path traversed by the evader, but not necessarily the path itself. In the third essay, we assume that the evader selects its path based on some unknown (to the interdictor) ranking criteria, but the interdictor observes the complete evasion path in each time period. For both settings, we design interdiction policies that minimize the number of time periods it takes a policy to recover a full information interdiction decision based on the underlying information feedback.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
6 September 2022 |
| Date Type: |
Publication |
| Defense Date: |
15 July 2022 |
| Approval Date: |
6 September 2022 |
| Submission Date: |
18 July 2022 |
| Access Restriction: |
2 year -- Restrict access to University of Pittsburgh for a period of 2 years. |
| Number of Pages: |
170 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Swanson School of Engineering > Industrial Engineering |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
no keywords |
| Related URLs: |
|
| Date Deposited: |
06 Sep 2022 16:38 |
| Last Modified: |
06 Sep 2022 16:38 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/43332 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}