学术报告报告主题: An effective Benders decomposition algorithm for the probabilistic set covering problem
报 告 人: 陈伟坤 特别副研究员
报告时间： 2025年 11月30日（星期日）上午11: 00-11: 45
报告地点： 清清文理楼3A02
邀 请 人: 贲树军 副教授
欢迎广大师生前往！
数学学院
2025年11月27日
报告摘要：
In this talk, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effective Benders decomposition (BD) algorithm for solving large-scale PSCPs, which enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is independent of the scenario size; and (ii) the Benders cuts can be separated by an efficient combinatorial algorithm. For the special case that the random vector is a combination of several independent random blocks/subvectors, we explicitly take this kind of block structure into consideration and develop a more efficient BD algorithm. Numerical results on instances with up to one million scenarios demonstrate the effectiveness of the proposed BD algorithms over a black-box mixed integer programming solver’s branch-and-cut and automatic BD algorithms and a state-of-the-art algorithm in the literature.
报告人介绍：
陈伟坤，北京理工大学数学与统计学院特别副研究员 ，硕士生导师。2019年在中国科学院数学与系统科学研究院获得博士学位。主要研究兴趣是整数规划理论、算法与软件及其在无线通信、物流等领域中的应用。现为中国运筹学会算法与软件分会常务理事，中国运筹学会数学规划分会青年理事，在SIAM J. Optim., Eur. J. Oper. Res., ACM Trans. Math. Softw., IEEE J. Sel. Areas Commun.,IEEE Trans. Signal Process., IEEE Trans. Netw. Service Manag.等杂志发表数篇学术论文。2018年获得中国运筹学会“科学技术奖运筹应用奖”，2020年获得中国科学院“中国科学院优秀博士学位论文”。担任《Journal of Global Optimization》客座编委，《运筹学学报（中英文）》编委。主持和参与国家自然科学青年、面上基金。