Branch-and-Price for Prescriptive Contagion Analytics

Alexandre Jacquillat (), Michael Lingzhi Li (), Martin Ramé () and Kai Wang ()
Additional contact information
Alexandre Jacquillat: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Michael Lingzhi Li: Harvard Business School, Harvard University, Cambridge, Massachusetts 02163
Martin Ramé: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Kai Wang: School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China

Operations Research, 2025, vol. 73, issue 3, 1558-1580

Abstract: 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 state-of-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.

Keywords: Optimization; contagion analytics; column generation; branch and price; dynamic programming; COVID-19 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0308 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:3:p:1558-1580

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().