•A novel probabilistic group-based centrality metric is introduced.•A mathematical optimization model to solve the problem is proposed.•Different versions of Benders decomposition are employed.•The ...computational results indicate the efficiency of our decomposition approach.
We introduce the stochastic pseudo-star degree centrality problem, which focuses on a novel probabilistic group-based centrality metric. The goal is to identify a feasible induced pseudo-star, which is defined as a collection of nodes forming a star network with a certain probability, such that it maximizes the sum of the individual probabilities of unique assignments between the star and its open neighborhood. The feasibility is measured as the product of the existence probabilities of edges between the center node and leaf nodes and the product of one minus the existence probabilities of edges among the leaf nodes. First, the problem is shown to be NP-complete. We then propose a non-linear binary optimization model subsequently linearized via McCormick inequalities. We test both classical and modern Benders Decomposition algorithms together with both two- and three-phase decomposition frameworks. Logic-based-Benders cuts are examined as alternative feasibility cuts when needed. The performance of our implementations is tested on small-world (SW) graphs and a real-world protein-protein interaction network. The SW networks resemble large-scale protein-protein interaction networks for which the deterministic star degree centrality has been shown to be an efficient centrality metric to detect essential proteins. Our computational results indicate that Benders implementations outperforms solving the model directly via a commercial solver in terms of both the solution time and the solution quality in every test instance. More importantly, we show that this new centrality metric plays an important role in the identification of essential proteins in real-world networks.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
One of the major challenges associated with applying Operations Research (OR) models to disrupting human trafficking networks is the limited amount of reliable data sources readily available for ...public use, since operations are intentionally hidden to prevent detection, and data from known operations are often incomplete. To help address this data gap, we propose a network generator for domestic sex trafficking networks by integrating OR concepts and qualitative research. Multiple sources regarding sex trafficking in the upper Midwest of the United States have been triangulated to ensure that networks produced by the generator are realistic, including law enforcement case file analysis, interviews with domain experts, and a survivor-centered advisory group with first-hand knowledge of sex trafficking. The output models the relationships between traffickers, so-called "bottoms", and victims. This generator allows operations researchers to access realistic sex trafficking network structures in a responsible manner that does not disclose identifiable details of the people involved. We demonstrate the use of output networks in exploring policy recommendations from max flow network interdiction with restructuring. To do so, we propose a novel conceptualization of flow as the ability of a trafficker to control their victims. Our results show the importance of understanding how sex traffickers react to disruptions, especially in terms of recruiting new victims.
► We examine a novel class of optimization problems that model restoring infrastructure systems. ► These new problems integrate network design and scheduling decisions. ► We utilize residual network ...optimality conditions in creating a dispatching rule. ► Our models and algorithms are tested on realistic case studies of infrastructure systems. ► The dispatching rule can be utilized in real-time restoration planning activities.
We consider the problem of restoring services provided by infrastructure systems after an extreme event disrupts them. This research proposes a novel integrated network design and scheduling problem that models these restoration efforts. In this problem, work groups must be allocated to build nodes and arcs into a network in order to maximize the cumulative weighted flow in the network over a horizon. We develop a novel heuristic dispatching rule that selects the next set of tasks to be processed by the work groups. We further propose families of valid inequalities for an integer programming formulation of the problem, one of which specifically links the network design and scheduling decisions. Our methods are tested on realistic data sets representing the infrastructure systems of New Hanover County, North Carolina in the United States and lower Manhattan in New York City. These results indicate that our methods can be used in both real-time restoration activities and long-term scenario planning activities. Our models are also applied to explore the effects on the restoration activities of aligning them with the goals of an emergency manager and to benchmark existing restoration procedures.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
•Arcs can be added to the network responding to interdictions.•Restructuring is modeled in city-level drug trafficking networks.•Column-and-constraint generation is improved upon to utilize partial ...information.•Computational analyses suggest MFNIP interdictions displace criminal activity.
We consider a new class of max flow network interdiction problems, where the defender is able to introduce new arcs to the network after the attacker has made their interdiction decisions. We prove properties of when this restructuring will not increase the value of the minimum cut, which has important practical interpretations for problems of disrupting drug trafficking networks. In particular, it demonstrates that disrupting lower levels of these networks will not impact their operations when replacing the disrupted participants is easy. For the bilevel mixed integer linear programming formulation of this problem, we devise a column-and-constraint generation (C&CG) algorithm to solve it. Our approach uses partial information on the feasibility of restructuring plans and is shown to be orders of magnitude faster than previous C&CG methods. We demonstrate that applying decisions from standard max flow network interdiction problems can result in significantly higher flows than interdictions that account for the restructuring.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
•We propose models for decentralization in interdependent infrastructure restoration.•We provide new mathematical formulations to capture restoration interdependencies.•We measure the loss in ...restoration effectiveness resulting from decentralization.•This loss can be greatly mitigated by having infrastructures share information.
We consider restoring multiple interdependent infrastructure networks after a disaster damages components in them and disrupts the services provided by them. Our particular focus is on interdependent infrastructure restoration (IIR) where both the operations and the restoration of the infrastructures are linked across systems. We provide new mathematical formulations of restoration interdependencies in order to incorporate them into an interdependent integrated network design and scheduling (IINDS) problem. The IIR efforts resulting from solving this IINDS problem model a centralized decision-making environment where a single decision-maker controls the resources of all infrastructures. In reality, individual infrastructures often determine their restoration efforts in an independent, decentralized manner with little communication among them. We provide algorithms to model various levels of decentralization in IIR efforts. These algorithms are applied to realistic damage scenarios for interdependent infrastructure systems in order to determine the loss in restoration effectiveness resulting from decentralized decision-making. Our computational tests demonstrate that this loss can be greatly mitigated by having infrastructures share information about their planned restoration efforts.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
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.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these ...services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Human trafficking is a serious crime and violation of human rights that results in numerous harms. Although the phenomenon is not new, scholarship on the issue has grown substantially since the first ...legal framework was passed in 2000. However, the existing literature has been criticized for its skewed focus on victims, among other things. The dearth of information on traffickers and their operations limits our ability to reduce or prevent perpetration. The current study presents a comprehensive and critical review of the existing literature focused on traffickers to synthesize what is already known and highlight the key gaps. Twenty-nine articles met the inclusion criteria of (1) focusing on traffickers and their operations and (2) relying on data either directly from traffickers or sources that contained detailed information about criminal cases against traffickers. We used an iterative process to identify relevant studies, which included collecting articles of which we were already familiar or were identified in existing reviews, searching their reference lists, and conducting cited-by searches until saturation was reached. Topics found in the extant literature included: characteristics of traffickers, relationships between traffickers and victims, organizational characteristics and networks, operations, connections with other crimes, motivations, perceptions of behavior, and risks associated with trafficking. It concludes with recommendations for future research and a discussion of how bridging gaps in the literature could support more rigorous mathematical modeling that is needed to identify and assess promising perpetration prevention and intervention strategies.
Full text
Available for:
NUK, OILJ, SAZU, UKNU, UL, UM, UPUK
This article focuses on the problem of interdicting layered networks that involve a physical flow network and an information flow network. There exist dependencies between these networks since ...components of the physical flow network are only operational should their counterparts in the information flow network receive enough demand. This leads to a network interdiction problem over these layered networks. The objective of the defender is to send the maximum amount of flow through its physical flow network. The objective of the attacker is to interdict components within the layered networks to minimize this maximum flow. For the case where the information supply arcs are uncapacitated, we apply a novel multi-step, dual-based reformulation technique. We apply this reformulation technique to two applications in order to provide policy-driven analysis: law enforcement efforts against illegal drug trafficking networks and cyber vulnerability analysis of infrastructure and supply chain networks. The computational results prove that our reformulation technique outperforms the traditional duality-based reformulation technique by orders of magnitude. This allows us to analyze instances of realistic size.
