Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance

In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes to increase the solution efficiency of the model as well as improved branch and bound strategies for implementation. Moreover, we simplify the model by eliminating some redundant integer variables. We propose an efficient solution algorithm called cut and prune method, which splits the feasible region into four equal subregions at each iteration and tries to eliminate subregions depending on the comparison of upper and lower bounds. When the sidelengths of the subregions are smaller than a predetermined value, the improved MIP model is solved to obtain the optimal solution. Computational experiments demonstrate that the solution time of the original MIP model is reduced substantially by the proposed solution approach.