Branch-and-Price for Prescriptive Contagion Analytics

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.