Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Essays on Interdiction Problems in Novel Settings

Yang, Jing (2022) Essays on Interdiction Problems in Novel Settings. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img] PDF
Restricted to University of Pittsburgh users only until 6 September 2024.

Download (947kB) | Request a Copy


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Yang, Jingj.yang@pitt.edujiy750000-0002-4651-810X
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairProkopyev, Olegdroleg@pitt.edu0000-0003-2888-8630
Committee MemberSaure, Denisdsaure@gmail.com0000-0002-8123-5009
Committee MemberBorrero, Juanjuan.s.borrero@okstate.edu0000-0001-8292-8838
Committee MemberZeng,
Committee MemberRajgopal,
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


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item