Branch-and-Price for Prescriptive Contagion Analytics

• 成果类型: Article
• 署名作者: Jacquillat, Alexandre; Li, Michael Lingzhi; Rame, Martin; Wang, Kai
• 署名单位: Massachusetts Institute of Technology (MIT); Harvard University; Massachusetts Institute of Technology (MIT); Tsinghua University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0308
• 发表日期: 2025
• 关键词: contagion analytics; Column Generation; branch and price; dynamic programming; Covid-19

摘要

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 contagion dynamics. These problems feature a large-scale mixed -integer nonconvex optimization structure with constraints governed by ordinary differential equations. This paper develops a branch -and -price methodology for this class of problems 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 tripartite branching scheme to circumvent nonlinearities. We apply the methodology to four real -world cases: vaccine distribution, vaccination centers deployment, content promotion, and congestion mitigation. Extensive experiments show that the algorithm scales to large and otherwise -intractable instances, outperforming stateof-the-art benchmarks. Our methodology provides practical benefits in contagion systems-In particular, we show that it can increase the effectiveness of a vaccination campaign in a setting replicating the rollout of COVID-19 vaccines in 2021. We provide an open -source implementation of the methodology to enable replication.