Title

Branch-and-Price for Prescriptive Contagion Analytics

Abstract

Predictive contagion models are ubiquitous in epidemiology, social sciences, engineering, and management. This paper formulates a prescriptive contagion analytics model where a decision-maker allocates shared resources across multiple segments of a population, each governed by continuous-time dynamics. We define four real-world problems under this umbrella: vaccine distribution, vaccination centers deployment, content promotion, and congestion mitigation. These problems feature a large-scale mixed-integer non-convex optimization structure with constraints governed by ordinary differential equations, combining the challenges of discrete optimization, non-linear optimization, and continuous-time system dynamics. This paper develops a branch-and-price methodology for prescriptive contagion analytics based on: (i) a set partitioning reformulation; (ii) a column generation decomposition; (iii) a state-clustering algorithm for discrete-decision continuous-state dynamic programming; and (iv) a tri-partite branching scheme to circumvent non-linearities. Extensive experiments show that the algorithm scales to very large and otherwise-intractable instances, outperforming state-of-the-art benchmarks. Our methodology provides practical benefits in contagion systems; in particular, it can increase the effectiveness of a vaccination campaign by an estimated 12-70\%, resulting in 7,000 to 12,000 extra saved lives over a three-month horizon mirroring the COVID-19 pandemic.

Bio

Alexandre Jacquillat is an Associate Professor of Operations Research and Statistics at the MIT Sloan School of Management. His research focuses on data-driven decision-making, spanning integer optimization, stochastic optimization, and machine learning. His primary focus is on the optimization of complex transportation and logistics systems to promote efficient, reliable and sustainable mobility of people and goods. Alexandre is the recipient of several awards, including the INFORMS Dantzig Dissertation Award, the Best Paper Prize from INFORMS Transportation Science and Logistics (twice), the Harvey Greenberg Research Award from INFORMS Computing, the Pierskalla Best Paper Award from INFORMS Health Applications, and the Best Paper Award from INFORMS Data Mining and Decision Analytics. He received a Master of Science in Applied Mathematics from the Ecole Polytechnique and PhD in Engineering Systems from MIT.