Compact MILP Formulations for the Maximum Availability Location Problem

This paper considers the maximum availability location problem (MALP) that attempts to deploy a limited number of facilities to maximize the weighted sum of covered targets while ensuring a guaranteed reliability level for those targets, and investigates the compact mixed integer linear programming (MILP) formulations for it. In particular, we first review two existing MILP formulations for the MALP, where the numbers of variables and constraints in one formulation are one order of magnitude smaller than those in the other, and establish the equivalence between their linear programming relaxations. This theoretical analysis demonstrates the advantage of using the compact formulation to solve MALPs by off-the-shelf MILP solvers, compared to the looser formulation. Then, we develop two preprocessing techniques to further simplify the compact formulation. The proposed preprocessing techniques can effectively eliminate the variables from the compact formulation, leading to a more compact MILP formulation that is much more computationally solvable by state-of-the-art MILP solvers. Numerical results demonstrate the effectiveness of the proposed compact MILP formulation in solving large-scale MALPs.