SDP-based Benders decomposition for solving p-median quadratic facility location problems
提出一种结合半定规划松弛的Benders分解算法，求解考虑设施间距离的p-中位数二次设施选址问题，数值实验表明该方法优于线性化重构和经典Benders分解。
The p -median facility location problem involves selecting the locations for p facilities from a set of potential locations, to balance the trade-off between facility establishment costs and distance to end users. In this paper, we introduce an extension, named the p -median quadratic facility location problem, that also considers inter-facility distance—important in applications where the facilities serve as intermediate hubs linking sites in different regions. This creates a quadratic term in the objective that makes the problem nonlinear. We develop a Benders decomposition method that uses a tight semi-definite programming relaxation of the Benders master problem, instead of solving the nonlinear master problem directly. We incorporate this decomposition strategy into a branch and bound framework to ensure convergence. Our numerical results show that this method outperforms the linear reformulation and classical Benders decomposition techniques, working independently or in tandem. • A quadratic facility location model for facilities that serve as intermediate hubs. • An algorithm based on Benders decomposition and semi-definite programming relaxation. • Semi-definite programming provides tight relaxations for the master problem. • New algorithm outperforms linearization and classical Benders decomposition.