An efficient branch-and-cut algorithm for the minimum covering location problem with distance constraints

We consider the minimum covering location problem with distance constraints (MCLPDC), which attempts to locate a set of undesirable facilities subject to the minimum distance constraints between any pair of located facilities while minimizing the negative impact caused by these facilities. The mixed integer programming (MIP) formulations of the MCLPDC are difficult to be solved by state-of-the-art MIP solvers due to the poor linear programming (LP) relaxation and the large problem size. To bypass the difficulties, we propose two families of valid inequalities for the MCLPDC. The proposed inequalities can effectively strengthen the LP relaxation of the MCLPDC and enable to provide a compact MIP formulation for the MCLPDC that has a potentially much smaller problem size. Moreover, we propose an efficient branch-and-cut algorithm, which starts with the compact MIP formulation and separates the exponential family of inequalities on the fly. Computational results on benchmark instances show that thanks to the tight LP relaxation and small problem size of the formulation, the proposed branch-and-cut algorithm outperforms a state-of-the-art approach by at least one order of magnitude.