Reformulation for a two-stage robust facility location problem

International audienceIn this paper, we consider a Facility Location Problem (FLP) in which the demand of each client is not completely known at decision time and the assignment of facilities to clients is postponed to a wait-and-see phase, as it typically happens in practical contexts. This problem can naturally be modeled as a two-stage robust problem with discrete uncertainty set and mixed-integer wait-and-see decisions. This class of problems is typically hard to solve and no satisfying exact approach has emerged in the literature. Our main contribution is to develop a non-trivial reformulation for this problem which can exactly be solved by recent advances on cost-uncertain two-stage robust problems. From a computational viewpoint, we show that our approach is able to solve medium size instances to proven optimality