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


Lower Bounds for the Uncapacitated Facility Location Problem with User Preferences

, et

We consider the bilevel uncapacitated facility location problem with user preferences. It is known that this model may be reformulated as a one-level location problem with some additional constraints. In this paper we introduce a new reformulation and show that this reformulation dominates three previous ones from the point of view of their linear programming relaxations and may be worse than a reduction to the row selection problem for pairs of matrices. However, this last reduction requires many additional variables and constraints. Computational experiments on random data instances shows that the new reformulation allows to find an optimal solution of the bilevel location problem considered faster than all previous approaches.

, 13 pages