上海管理论坛第505期

题目：覆盖约束p-中值问题的Benders分解算法

演讲人：戴彧虹教授，中科院数学与系统研究院

主持人：林贵华教授，8188威尼斯娱人城管理学院

时间：2023年10月12日（周四），下午15:00

地点：8188威尼斯娱人城校本部东区管理学院420室

主办单位：8188威尼斯娱人城管理学院、8188威尼斯娱人城管理学院青年教师联谊会

演讲人简介：

国际知名优化专家，中科院数学与系统研究院研究员、副院长。

中国运筹学会理事长，亚太运筹学会联合会主席。

主持国家杰青项目、重点研发计划项目、创新研究群体项目等。

曾获国家自然科学二等奖、中国青年科技奖、钟家庆数学奖、冯康科学计算奖、陈省身数学奖、首届萧树铁应用数学奖等。

演讲内容简介：

In this talk, we study the p-median problem with the addition of a coverage constraint which requires the total customer demand, covered at a distance greater than a prespecified coverage distance, to be smaller than or equal to a given threshold. We propose an efficient Benders decomposition (BD) approach for solving large-scale problems. We show that both Benders feasibility and optimality cuts can be separated in efficient combinatorial polynomial-time algorithms. Moreover, we enhance the BD approach by using tight initial cuts to initialize the relaxed master problem, implementing an effective two-stage algorithm to find high-quality solutions, and adding valid inequalities to strengthen the problem formulation. Computational results on benchmark instances show that the proposed BD approach outperforms the state-of-the-art general-purpose MIP solver's branch-and-cut and automatic BD algorithms by at least one order of magnitude.

欢迎广大师生参加！