 An efficient benders decomposition for the p-median problemCristian Duran-Mateluna, Zacharie Ales and Sourour Elloumi European Journal of Operational Research, 2023, vol. 308, issue 1, 84-96 Abstract: The p-median problem is a classic discrete location problem with numerous 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 show that the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm that outperforms state-of-the-art methods on benchmark instances by an order of magnitude and allows to exactly solve for the first time several instances among which are large TSP instances and BIRCH instances. We also show that our implementation easily applies to the uncapacitated facility location problem. Keywords: Location; p-Median problem; Benders decomposition; Integer programming formulation; Polynomial separation algorithm (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:308:y:2023:i:1:p:84-96 DOI: 10.1016/j.ejor.2022.11.033 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.