Redesigning Benders Decomposition for Large-Scale Facility Location

The uncapacitated facility location (UFL) problem is one of the most famous and most studied problems in the operations research literature. Given a set of potential facility locations and a set of customers, the goal is to find a subset of facility locations to open and to allocate each customer to open facilities so that the facility opening plus customer allocation costs are minimized. In our setting, for each customer the allocation cost is assumed to be a linear or separable convex quadratic function. Motivated by recent UFL applications in business analytics, we revise approaches that work on a projected decision space and hence are intrinsically more scalable for large-scale input data. Our working hypothesis is that many of the exact (decomposition) approaches that were proposed decades ago and discarded soon after need to be redesigned to take advantage of the new hardware and software technologies. To this end, we “thin out” the classical models from the literature and use (generalized) Benders cuts to replace a huge number of allocation variables by a small number of continuous variables that model the customer allocation cost directly. Our results show that Benders decomposition allows for a significant boost in the performance of a mixed-integer programming solver. We report the optimal solution of a large set of previously unsolved benchmark instances widely used in the available literature. In particular, dramatic speedups are achieved for UFL problems with separable quadratic allocation costs, which turn out to be much easier than their linear counterparts when our approach is used. This paper was accepted by Yinyu Ye, optimization.