Solution of Stochastic Facility Location Problems with Combinatorially many Decision-Dependent Distributions

This article describes a model and an exact solution method for facility location problems with decision-dependent uncertainties. The model allows characterizing the probability distribution of the random elements as a function of the choice of open facilities. This, in turn, generates a combinatorial number of potential distributions of the random elements. Though general in the relationship between location decisions and distributions, the proposed model is, however, exponential in size. We show that the problem can be solved efficiently by a recent finitely convergent method for stochastic programs with decision-dependent uncertainty, for which we tight prove cutting planes and efficient valid inequalities. Extensive tests show that facility location problems with up to 2¹⁷ potential distributions and hundreds of thousand scenarios are solved within minutes. These results indentify a promising solution strategy for other combinatorial optimization problems characterized by decision-dependent uncertanty.