An official website of the United States government
We consider a new class of multi-period network interdiction problems, where interdiction and restructuring decisions are decided upon before the network is operated and implemented throughout the time horizon.We discuss how we apply this new problem to disrupting domestic sex trafficking networks, and introduce a variant where a second cooperating attacker has the ability to interdict victims and prevent the recruitment of prospective victims. This problem is modeled as a bilevel mixed integer linear program (BMILP), and is solved using column-and-constraint generation with partial information. We also simplify the BMILP when all interdictions are implemented before the network is operated. Modeling-based augmentations are proposed to significantly improve the solution time in a majority of instances tested. We apply our method to synthetic domestic sex trafficking networks, and discuss policy implications from our model. In particular, we show how preventing the recruitment of prospective victims may be as essential to disrupting sex trafficking as interdicting existing participants.
more »
« less
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.
more »
« less
- Award ID(s):
- 2039584
- PAR ID:
- 10653590
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- INFORMS Journal on Computing
- ISSN:
- 1091-9856
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upper-level problem, assuming that a follower chooses an optimal reaction by solving a lower-level problem. However, in many settings, the lower-level problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader’s actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lower-level problem, either approximately or heuristically. Thus, the leader can hedge against the follower’s use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defender-attacker problems.more » « less
-
We study the mean-standard deviation minimum cost flow (MSDMCF) problem, where the objective is minimizing a linear combination of the mean and standard deviation of flow costs. Due to the nonlinearity and nonseparability of the objective, the problem is not amenable to the standard algorithms developed for network flow problems. We prove that the solution for the MSDMCF problem coincides with the solution for a particular mean-variance minimum cost flow (MVMCF) problem. Leveraging this result, we propose bisection (BSC), Newton–Raphson (NR), and a hybrid (NR-BSC)—method seeking to find the specific MVMCF problem whose optimal solution coincides with the optimal solution for the given MSDMCF problem. We further show that this approach can be extended to solve more generalized nonseparable parametric minimum cost flow problems under certain conditions. Computational experiments show that the NR algorithm is about twice as fast as the CPLEX solver on benchmark networks generated with NETGEN.more » « less
-
Network alignment is a fundamental task in many high-impact applications. Most of the existing approaches either explicitly or implicitly consider the alignment matrix as a linear transformation to map one network to another, and might overlook the complicated alignment relationship across networks. On the other hand, node representation learning based alignment methods are hampered by the incomparability among the node representations of different networks. In this paper, we propose a unified semi-supervised deep model (ORIGIN) that simultaneously finds the non-rigid network alignment and learns node representations in multiple networks in a mutually beneficial way. The key idea is to learn node representations by the effective graph convolutional networks, which subsequently enable us to formulate network alignment as a point set alignment problem. The proposed method offers two distinctive advantages. First (node representations), unlike the existing graph convolutional networks that aggregate the node information within a single network, we can effectively aggregate the auxiliary information from multiple sources, achieving far-reaching node representations. Second (network alignment), guided by the highquality node representations, our proposed non-rigid point set alignment approach overcomes the bottleneck of the linear transformation assumption. We conduct extensive experiments that demonstrate the proposed non-rigid alignment method is (1) effective, outperforming both the state-of-the-art linear transformation-based methods and node representation based methods, and (2) efficient, with a comparable computational time between the proposed multi-network representation learning component and its single-network counterpart.more » « less
-
We consider a class of convex decentralized consensus optimization problems over connected multi-agent networks. Each agent in the network holds its local objective function privately, and can only communicate with its directly connected agents during the computation to find the minimizer of the sum of all objective functions. We propose a randomized incremental primal-dual method to solve this problem, where the dual variable over the network in each iteration is only updated at a randomly selected node, whereas the dual variables elsewhere remain the same as in the previous iteration. Thus, the communication only occurs in the neighborhood of the selected node in each iteration and hence can greatly reduce the chance of communication delay and failure in the standard fully synchronized consensus algorithms. We provide comprehensive convergence analysis including convergence rates of the primal residual and consensus error of the proposed algorithm, and conduct numerical experiments to show its performance using both uniform sampling and important sampling as node selection strategy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1287/ijoc.2023.0423
