An exact method for the bi-objective p-median max-sum diversity problem

This paper introduces a bi-objective facility location problem with two potentially conflicting objectives. The first objective is to minimize the total distance between p selected facilities and the end users they serve (commonly referred to as the p-median objective). The second objective is to maximize the total distance between the selected facilities (commonly referred to as the max-sum diversity objective). We name this problem the bi-objective p-median max-sum diversity problem. The problem follows the bi-level max-sum framework by including a dispersion constraint that prevents selecting two facilities that are within a certain specified distance of each other. If this distance is too large, then the problem is infeasible. Determining an upper bound for feasibility requires solving a max-min dispersion problem, and we develop an improved bi-section search algorithm for doing this, which is more efficient than current exact methods. Then, for the bi-objective p-median max-sum diversity problem (with a fixed value for the distance cut-off in the dispersion constraint), we develop an exact algorithm based on the ϵ-constraint method for determining all Pareto optimal solutions. This involves repeatedly solving a subproblem with quadratic constraints (arising from the quadratic diversity objective) using tangent cutting planes and Benders decomposition. Computational results using the GKD-d dataset show that our exact method is effective for large instances with up to 500 locations.