An efficient Benders decomposition for the p-median problem - ENSTA Paris - École nationale supérieure de techniques avancées Paris Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

An efficient Benders decomposition for the p-median problem

Résumé

The p-median problem is a classic discrete location problem with several applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We prove that the Benders cuts can be separated by a polynomial time algorithm. The Benders decomposition also leads to a new compact formulation for the p-median problem. We implement a branch-and-Benders-cut approach that outperforms state-of-the-art methods on benchmark instances by an order of magnitude.
Fichier principal
Vignette du fichier
Preprint - An efficient Benders decomposition for the p-median problem.pdf (395.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03450829 , version 1 (26-11-2021)
hal-03450829 , version 2 (08-12-2021)
hal-03450829 , version 3 (21-11-2022)

Identifiants

Citer

Cristian Durán Mateluna, Zacharie Alès, Sourour Elloumi. An efficient Benders decomposition for the p-median problem. 2021. ⟨hal-03450829v1⟩
212 Consultations
117 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More