Titre :

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

Auteur(s) :

Gendron, Bernard [Auteur]
Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT]
Khuong, Paul-Virak [Auteur]
Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT]
Semet, Frédéric [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Integrated Optimization with Complex Structure [INOCS]

Titre de la manifestation scientifique :

ROADEF 2017 - 18ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision

Ville :

Metz

Pays :

France

Date de début de la manifestation scientifique :

2017-02-22

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In this talk, we study and compare several formulations for the two-level uncapacitatedfacility location problem with single assignment constraints (TUFLP-S), an extension of theuncapacitated facility location problem ...
Lire la suite >In this talk, we study and compare several formulations for the two-level uncapacitatedfacility location problem with single assignment constraints (TUFLP-S), an extension of theuncapacitated facility location problem (UFLP) [4]. The UFLP consists in selecting a set ofdepots from potential locations in order to minimize an objective function that includes fixedcosts 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 issubstituted with two tiers of locations (depots and satellites), and the path to each customermust begin at a depot and transit by a satellite. The objective function includes fixed costsassociated with the depots and the satellites, fixed costs for establishing connections betweendepots and satellites, and transportation costs from any depot to each customer, i.e., each pathof the form depot-satellite-customer has a corresponding transportation cost. The TUFLP-Simposes 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 instancesfor which the single assignment constraints are not explicitly enforced, there is an optimalsolution 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 toderive an initial MIP formulation for the TUFLP-S. We then propose five additional MIPformulations based on reformulation techniques and on the relaxation of the integrality of someof the variables associated with location decisions. One of these formulations was previouslyconsidered in [3] to derive a Lagrangian relaxation for the TUFLP-S. We theoretically comparethe LP relaxations of these models. Then, we compare the models by solving a large numberof various instances with a state-of-the-art MIP solver. The results show that, whenever fixedcosts at the depots (at the satellites) are significant, it is beneficial to keep the integrality of thecorresponding binary variables, but to relax the integrality of the binary variables associatedwith the satellites (with the depots). In our experiments, poor results are obtained by thereformulation that minimizes the number of binary variables by relaxing the integrality of thetwo types of location variables.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Nationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL