Groupe d’études et de recherche en analyse des décisions

G-2020-49

Data-driven distributionally robust capacitated facility location problem

et

We study a distributionally robust version of the classical capacitated facility location problem with a distributional ambiguity set defined as a Wasserstein ball around an empirical distribution constructed based on a small data sample. Both single- and two-stage problems are addressed, with customer demands being the uncertain parameter. For the single-stage problem, we provide a direct reformulation into a mixed-integer program. For the two-stage problem, we develop two iterative algorithms, based on column generation, for solving the problem exactly. We also present conservative approximations based on support set relaxation for the single- and two-stage problems, an affine decision rule approximation of the two-stage problem, and a relaxation of the two-stage problem based on support set restriction. Numerical experiments on benchmark instances show that the exact solution algorithms are capable of solving large scale problems efficiently. The different approximation schemes are numerically compared and the performance guarantee of the two-stage problem's solution on out-of-sample data is analyzed.

, 28 pages