Models and Relaxations for Two-Level Uncapacitated Facility Location with Single-Assignment

Abstract : In this talk, we study and compare several formulations for the two-level uncapacitated facility location problem with single assignment constraints (TUFLP-S), an extension of the uncapacitated facility location problem (UFLP) [4]. The UFLP consists in selecting a set of depots from potential locations in order to minimize an objective function that includes fixed costs associated with each depot and transportation costs from any depot to each customer. In the two-level uncapacitated facility location problem (TUFLP), the single set of locations is substituted with two tiers of locations (depots and satellites), and the path to each customer must begin at a depot and transit by a satellite. The objective function includes fixed costs associated with the depots and the satellites, fixed costs for establishing connections between depots and satellites, and transportation costs from any depot to each customer, i.e., each path of the form depot-satellite-customer has a corresponding transportation cost. The TUFLP-S imposes the additional restriction that each satellite can be connected to at most one depot. These single assignment constraints appear in a number of applications, most notably in trans- portation [5] and telecommunications [2]. Note also that, for a large class of TUFLP instances for which the single assignment constraints are not explicitly enforced, there is an optimal solution that satisfies these constraints, due to the structure of the objective function [2]. First, we present a general formulation for the TUFLP [1], and we adapt this model to derive an initial MIP formulation for the TUFLP-S. We then propose five additional MIP formulations based on reformulation techniques and on the relaxation of the integrality of some of the variables associated with location decisions. One of these formulations was previously considered in [3] to derive a Lagrangian relaxation for the TUFLP-S. We theoretically compare the LP relaxations of these models. Then, we compare the models by solving a large number of various instances with a state-of-the-art MIP solver. The results show that, whenever fixed costs at the depots (at the satellites) are significant, it is beneficial to keep the integrality of the corresponding binary variables, but to relax the integrality of the binary variables associated with the satellites (with the depots). In our experiments, poor results are obtained by the reformulation that minimizes the number of binary variables by relaxing the integrality of the two types of location variables.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download
Contributor : Frédéric Semet <>
Submitted on : Thursday, December 14, 2017 - 4:47:28 PM
Last modification on : Wednesday, April 17, 2019 - 12:15:36 PM


  • HAL Id : hal-01664273, version 1


Bernard Gendron, Paul-Virak Khuong, Frédéric Semet. Models and Relaxations for Two-Level Uncapacitated Facility Location with Single-Assignment. ROADEF 2017 - 18ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. ⟨hal-01664273⟩



Record views