Models for Removing Links in a Network to Minimize the Spread of Infections

/in , /by

Minimizing the spread of infections is a challenging problem, and it is the subject matter in many different fields such as epidemiology and cyber-security. In this paper, we investigate link removal as an intervention strategy and study the relative effectiveness of different link removal methods in minimizing the spread of infections in a network. With that in mind, we develop four connectivity-based network interdiction models and formulate these models as mixed integer linear programs. The first model minimizes the number of connections between infected and susceptible nodes; the second the number of susceptible nodes having one or more connections with infected nodes; the third the total number of paths between infected and susceptible nodes; and the fourth the total weight of the paths between infected and susceptible nodes. We also propose heuristic algorithms to solve the models. The network interdiction models act as link removal methods, i.e., each return a solution consisting of a set of links to remove in the network. We compare the effectiveness of these four methods with the effectiveness of an existing link removal method, a method based on link betweenness centrality, and random link removal method. Our results show that complete isolation of susceptible nodes from infected nodes is the most effective method in reducing the average number of new infections (reduce occurrence) under most scenarios, and the relative effectiveness of the complete isolation method increases with transmission probability. In contrast, removing the highest probability transmission paths is the most effective method in increasing the average time to infect half of the susceptible nodes (reduce speed) under most scenarios, and the relative effectiveness of this method decreases with transmission probability.

Allocating Protection Resources to Facilities When the Effect of Protection is Uncertain

/in , /by

We study a new facility protection problem in which one must allocate scarce protection resources to a set of facilities given that allocating resources to a facility only has a probabilistic effect on the facility’s post-disruption capacity. This study seeks to test three common assumptions made in the literature on modeling infrastructure systems subject to disruptions: 1) perfect protection, e.g., protecting an element makes it fail-proof, 2) binary protection, i.e., an element is either fully protected or unprotected, and 3) binary state, i.e., disrupted elements are fully operational or non-operational. We model this facility protection problem as a two-stage stochastic program with endogenous uncertainty. Because this stochastic program is non-convex we present a greedy algorithm and show that it has a worst-case performance of 0.63. However, empirical results indicate that the average performance is much better. In addition, experimental results indicate that the mean-value version of this model, in which parameters are set to their mean values, performs close to optimal. Results also indicate that the perfect and binary protection assumptions together significantly affect the performance of a model. On the other hand, the binary state assumption was found to have a smaller effect.

The wireless network jamming problem subject to protocol interference

/in , /by

We study the following questions related to wireless network security: Which jammer placement configuration during a jamming attack results in the largest degradation of network throughput? and Which network design strategies are most effective in mitigating a jamming attack? Although others have studied similar jammer placement problems, this article is the first to optimize network throughput subject to radio wave interference. We formulate this problem as a bi-level mixed-integer program, and solve it using a cutting plane approach that is able to solve networks with up to 81 transmitters, which is a typical size for studies in wireless network optimization. Experiments with the algorithm also yielded the following insights into wireless network jamming: (1) increasing the number of channels is the best strategy for designing a network that is robust against jamming attacks, and (2) increasing the range of the jammer is the best strategy for the attacker.

A Bi-objective Analysis of the R-All-Neighbor P-Center Problem

/in , /by

In this paper we consider a generalization of the p-center problem called the r-all-neighbor p-center problem (RANPCP). The objective of the RANPCP is to minimize the maximum distance from a demand point to its r  th-closest located facility. The RANPCP is applicable to facility location with disruptions because it considers the maximum transportation distance after (r-1) facilities are disrupted. While this problem has been studied from a single-objective perspective, this paper studies two bi-objective versions. The main contributions of this paper are (1) algorithms for computing the Pareto-efficient sets for two pairs of objectives (closest distance vs rth-closest distance and cost vs. rth-closest distance) and (2) an empirical analysis that gives several useful insights into the RANPCP. Based on the empirical results, the RANPCP produces solutions that not only minimize vulnerability but also perform reasonably well when disruptions do not occur. In contrast, if disruptions are not considered when locating facilities, the consequence due to facility disruptions is much higher, on average, than if disruptions had been considered. Thus, our results show the importance of optimizing for vulnerability. Therefore, we recommend a bi-objective analysis.

A Multi-objective Integrated Facility Location-Hardening Model: Analyzing the Pre- and Post-Disruption Tradeoff

/in , /by

Two methods of reducing the risk of disruptions to distribution systems are (1) strategically locating facilities to mitigate against disruptions and (2) hardening facilities. These two activities have been treated separately in most of the academic literature. This article integrates facility location and facility hardening decisions by studying the minimax facility location and hardening problem (MFLHP), which seeks to minimize the maximum distance from a demand point to its closest located facility after facility disruptions. The formulation assumes that the decision maker is risk averse and thus interested in mitigating against the facility disruption scenario with the largest consequence, an objective that is appropriate for modeling facility interdiction. By taking advantage of the MFLHP’s structure, a natural three-stage formulation is reformulated as a single-stage mixed-integer program (MIP). Rather than solving the MIP directly, the MFLHP can be decomposed into sub-problems and solved using a binary search algorithm. This binary search algorithm is the basis for a multi-objective algorithm, which computes the Pareto-efficient set for the pre- and post-disruption maximum distance. The multi-objective algorithm is illustrated in a numerical example, and experimental results are presented that analyze the tradeoff between objectives.

Robust Facility Location: Hedging Against Failures

/in , /by

While few companies would be willing to sacrifice day-to-day operations to hedge against disruptions, designing for robustness can yield solutions that perform well before and after failures have occurred. Through a multi-objective optimization approach this paper provides decision makers the option to trade-off total weighted distance before and after disruptions in the Facility Location Problem. Additionally, this approach allows decision makers to understand the impact on the opening of facilities on total distance and on system robustness (considering the system as the set of located facilities). This approach differs from previous studies in that hedging against failures is done without having to elicit facility failure probabilities concurrently without requiring the allocation of additional hardening/protections resources. The approach is applied to two datasets from the literature.

Transportation-Research

Vulnerability Assessment and Re-routing of Freight Trains Under Disruptions: A Coal Supply Chain Network Application

/in , /by

In this paper, we present a two-stage mixed integer programming (MIP) interdiction model in which an interdictor chooses a limited amount of elements to attack first on a given network, and then an operator dispatches trains through the residual network. Our MIP model explicitly incorporates discrete unit flows of trains on the rail network with time-variant capacities. A real coal rail transportation network is used in order to generate scenarios to provide tactical and operational level vulnerability assessment analysis including rerouting decisions, travel and delay costs analysis, and the frequency of interdictions of facilities for the dynamic rail system.

Models for reducing the risk of critical networked infrastructures

/in , /by

In this paper, we review the literature studying how to reduce the disruption risk to critical networked infrastructures. This is an important area of research because huge consequences result from infrastructure disruptions. As a result, this research area has grown a lot in the last decade. In this review we discuss articles from the literature, place them into categories, and suggest topics for future research. Our review shows that although this area is growing in popularity, there are still many important opportunities for future work.