Redesigning Benders Decomposition for Large-Scale Facility Location

Matteo Fischetti (), Ivana Ljubić () and Markus Sinnl ()
Additional contact information
Matteo Fischetti: Department of Information Engineering, University of Padua, 35131 Padova, Italy
Ivana Ljubić: IDS Department, ESSEC Business School of Paris, 95021 Cergy Pontoise Cedex, France
Markus Sinnl: Department of Statistics and Operations Research, University of Vienna, 1090 Vienna, Austria

Management Science, 2017, vol. 63, issue 7, 2146-2162

Abstract: 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.

Keywords: facility; location; •; generalized; Benders; decomposition; •; nonlinear; programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (44)

Downloads: (external link)
https://doi.org/10.1287/mnsc.2016.2461 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:63:y:2017:i:7:p:2146-2162

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().