题目:覆盖约束p-中值问题的Benders分解算法
演讲人:戴彧虹教授,中科院数学与系统研究院
主持人:林贵华教授,上海大学管理学院
时间:2023年10月12日(周四),下午15:00
地点:上海大学校本部东区管理学院420室
主办单位:上海大学管理学院、上海大学管理学院青年教师联谊会
演讲人简介:
国际知名优化专家,中科院数学与系统研究院研究员、副院长。
中国运筹学会理事长,亚太运筹学会联合会主席。
主持国家杰青项目、重点研发计划项目、创新研究群体项目等。
曾获国家自然科学二等奖、中国青年科技奖、钟家庆数学奖、冯康科学计算奖、陈省身数学奖、首届萧树铁应用数学奖等。
演讲内容简介:
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.
欢迎广大师生参加!