A Bilevel Network Interdiction Problem to Minimize the Number of Active Special Arcs in the Maximum Flow
研究一个双层网络阻断问题，下层求解最大流，上层最小化关键弧集中有正流量的弧数，应用于人口贩卖阻断，提出了乐观和悲观变体的单层重构，并针对悲观问题设计了高效算法。
We consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node, and the leader aims to minimize the number of arcs from a critical set that have positive flow on them, that is, active arcs, in the maximum flow solution obtained by the follower. This problem is motivated by an application in human trafficking disruption. We consider both the optimistic and pessimistic variants of this bilevel optimization problem and develop their respective single-level reformulations. We present a tailored solution method to the pessimistic problem, which solves the problem to optimality for one practically important class of networks. Through computational experiments on randomly generated layered network instances, we show the effectiveness of the proposed methods and demonstrate that the tailored method is orders of magnitude faster than existing approaches in the literature. We also conduct computational experiments on randomly generated test instances inspired by domestic human trafficking networks and draw domain-specific insights. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the National Science Foundation [Grant 2039584]. The computational experiments discussed in this paper were performed on the Palmetto Computing Cluster. The Palmetto Computing Cluster is supported by the National Science Foundation [Grants MRI# 2024205, MRI# 1725573, and CRI# 2010270]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0423 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0423 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .