2024年06月17日 星期一 登录 EN

学术活动
Benders decomposition for coverage constrained p-median problems
首页 - 学术活动
报告人:
Weikun Chen, Assistant Professor, School of Mathematics and Statistics Beijing Institute of Technology
邀请人:
Yafeng Liu, Associate Professor
题目:
Benders decomposition for coverage constrained p-median problems
时间地点:
15:30-16:30 May 30 (Tuesday), Z311
摘要:
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.