Lower Bounds for the Uncapacitated Facility Location Problem with User Preferences

Abstract

Abstract. We consider the bilevel uncapacitated facility location problem with user pref-erences. 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 re-formulation allows to find an optimal solution of the bilevel location problem considered faster than all previous approaches. Key words. Bilevel programming, facility location, pseudo-Boolean function, duality gap. 1