An efficient Benders decomposition for the p-median problem - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2022

An efficient Benders decomposition for the p-median problem

(1, 2, 3) , (1, 2) , (1, 2)
1
2
3

Abstract

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
p_median_Benders.pdf (428.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

Cristian Durán Mateluna, Zacharie Alès, Sourour Elloumi. An efficient Benders decomposition for the p-median problem. European Journal of Operational Research, 2022, ⟨10.1016/j.ejor.2022.11.033⟩. ⟨hal-03450829v3⟩
100 View
39 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More