图 基于常微分方程的动态系统下的决策问题示意
传播模型(如SIR、SEIR模型)广泛存在于传染病学、管理科学与工程、工商管理等研究中,被用于刻画流行病传染、交通拥堵传播以及营销推广等现象。然而,基于传播模型的决策优化问题由于其复杂结构特征面临有效求解的严峻挑战,亟待提出更有效的决策优化方法。
在国家自然科学基金项目(批准号:72322002、72331001、72361137001)资助下,清华大学车辆与运载学院王凯助理教授团队与麻省理工学院以及哈佛大学研究团队合作,首次将经典大规模分解式优化算法引入高效求解基于传播模型的决策优化问题,取得了以下创新成果:
(1)针对考虑连续时间传播动力学的有限资源多区域配置优化问题(图),分析问题复杂特征并构建了包含常微分方程约束的大规模混合整数非凸优化模型。
(2)基于传统大规模优化算法和模型特征,提出了基于集合划分、列生成分解、面向离散决策与连续状态下动态规划的状态聚类算法以及三叉搜索分支方法的分支定价精确算法。
(3)应用所提出决策优化方法开展疫苗分配、疫苗接种中心部署、内容推广和交通拥堵控制相关数值实验,表明所提出的优化方法可降低疫情中人员伤亡率10%-70%,相比已有最好算法具有6%–12%的求解优势,验证了所提出优化方法的有效性和普适性。
上述研究成果以“面向规范性传播分析的分支定价算法(Branch-and-Price for Prescriptive Contagion Analytics)”为题,于2024年3月在管理科学领域国际期刊《运筹学》(Operations Research)发表。论文链接:https://doi.org/10.1287/opre.2023.0308。
该研究可为基于传播模型的复杂系统决策优化提供理论支持,对于我国提升疫情防控能力、改善交通拥堵、优化市场监管等具有重要指导意义。