查看文章

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 …