Branch-and-Price for Prescriptive Contagion Analytics

Contagion models are ubiquitous in epidemiology, social sciences, engineering, and management. This thesis formalizes prescriptive contagion analytics problems where a centralized decision-maker allocates shared resources across multiple segments of a population, each governed by contagion dynamics. We define four real-world problems under this umbrella: distributing vaccines, deploying vaccination centers, mitigating urban congestion, promoting online content, and combating drug addiction. Prescriptive contagion problems involve mixed-integer non-convex optimization models with constraints governed by ordinary differential equations, thus combining the challenges of combinatorial optimization, non-linear optimization, and continuous-time system dynamics. This thesis develops a branch-and-price methodology for these problems based on: (i) a set partitioning reformulation; (ii) a column generation decomposition; (iii) a novel state clustering algorithm for discrete-decision continuous-state dynamic programming; and (iv) a novel tri-partite branching scheme to circumvent non-linearities. Extensive experiments show that the algorithm scales to large and otherwise- intractable instances, significantly outperforming state-of-the-art benchmarks. Our methodology provides a novel decision-making tool to support resource allocation in contagion systems. In particular, its application can increase the effectiveness of vaccination campaigns by an estimated 50-70%, resulting in 12,000 extra saved lives over 12 weeks in a situation mirroring the COVID-19 pandemic.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Ramé, Martin

Advisor dc:contributor.advisor

• Jacquillat, Alexandre

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/151633

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/151633