Controlling Epidemicson Networks Using Stochastic Optimization Techniques
We study the problem of designing interventionstrategies (e.g. vaccinations), under budget constraints, to minimize thespread of an epidemic outbreak. This is a challenging stochastic optimizationproblem in the context of the SIR epidemic model on a network. Previousapproaches for this problem are either heuristics or approximation algorithmsfor restricted settings. We have developed a bicriteria approximation algorithmthat combines linear programming (LP) based rounding and the sample averageapproximation (SAA) technique from stochastic optimization. Our algorithmprovides empirical guarantees for the solution quality in graphs of moderatesize. We evaluate our approach on various networks such as syntheticagent-based populations, random networks (e.g., preferential attachment), andreal-world collaboration networks. Our results demonstrate that theinterventions computed by our algorithm outperform standard baseline heuristics(e.g., remove nodes with a high degree). Also, we show that our approachobtains near-optimal interventions in practice.
The main bottleneck of the SaaRound algorithm is using a solver toobtain a fractional optimal solution for the LP relaxation of the problem. Toovercome this, we developed an approximation algorithm, by adapting theMultiplicative Weights Update (MWU) method along with the SAA technique, suchthat it bypasses the need to use a solver, to approximately solve the LP.Furthermore, we provide a memory-efficient and scalable version of thisapproach, that allows scaling to very large networks corresponding to state-and country-level populations. We show that this algorithm is able to achievenear-optimal solutions to the LP in practice.
Further, we consider the case where components of the epidemicmodel (i.e., sources or source distribution) might not be known precisely. Insuch a setting, a min-max objective, where the goal is to minimize the maximumoutbreak size in any possible scenario, gives a more robust solution comparedto the interventions considered for a single scenario. We develop rigorousapproximation algorithms for this problem and evaluate its performance ondifferent random graphs.
Finally, we consider the problem of extending our approaches tocontrol problems in other epidemic models that follow the SIR classdynamics (e.g. SEI, SI). To this end, we developed a simple framework to extendour approach to such models. Particularly, we consider the problem of designinggroup-scale interventions, to control the spread of invasive alien species(IAS), that affect crops, across a landscape. Our goal here is to find a set ofregions to intervene, satisfying budget constraints, such that the spread ofIAS is minimized. Using our framework, we developed a bicriteriaapproximation algorithm for finding effective group-scale interventions forthis problem and show its performance guarantees.
- MadhavMarathe, Committee Chair
- Anil Vullikanti, Advisor
- B. Aditya Prakash
- Jundong Li
- Abhijin Adiga
- Michael D. Porter