An efficient Benders decomposition for the p-median problem

DOI10.1016/J.EJOR.2022.11.033MaRDI QIDQ6167396zbMATH OpenOpenAlexFDO

Authors Cristian Duran-Mateluna, Zacharie Ales, Sourour Elloumi

Publication date 10 July 2023

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.13405

zbMATH Keywords

\(p\)-median problemBenders decompositioninteger programming formulationlocationpolynomial separation algorithm

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

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.

Recommendations

• Analysis of decomposition algorithms with Benders cuts for p-median problem
• A branch decomposition algorithm for the p-median problem
• A tighter formulation of the p-median problem
• A Modified Benders Method for the Single- and Multiple Allocation P-Hub Median Problems
• A computational study for the p-median problem
• scientific article; zbMATH DE number 3915986
• scientific article; zbMATH DE number 4209907
• Approximation algorithms for the median problem in the breakpoint model
• On the linear relaxation of the \(p\)-median problem
• An approximation algorithm for the \(p\)-hub median problem

Cites work

• A Canonical Representation of Simple Plant Location Problems and Its Applications
• A computational study for the p-median problem
• A Dual-Bounded Algorithm for the p-Median Problem
• A hybrid heuristic for the \(p\)-median problem
• A scaleable projection-based branch-and-cut algorithm for the \(p\)-center problem
• A tighter formulation of the p-median problem
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• An adaptive multiphase approach for large unconditional and conditional \(p\)-median problems
• An aggregation heuristic for large scale p-median problem
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Benders decomposition for very large scale partial set covering and maximal covering location problems
• Computational study of large-scale p-median problems
• Location science
• Metaheuristic applications on discrete facility location problems: a survey
• Near-optimal large-scale k-medoids clustering
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Partitioning procedures for solving mixed-variables programming problems
• Solution methods for thep-median problem: An annotated bibliography
• Solving large \(p\)-median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search
• Solving large p-median problems with a radius formulation
• The p-Median Problem for Cluster Analysis: A Comparative Test Using the Mixture Model Approach
• The \(p\)-median problem: a survey of metaheuristic approaches
• The Benders decomposition algorithm: a literature review
• The Optimal Diversity Management Problem
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(11)

• Constructing a DC decomposition for ordered median problems
• BEAMR: an exact and approximate model for the p-median problem
• A Modified Benders Method for the Single- and Multiple Allocation P-Hub Median Problems
• The exam location problem: mathematical formulations and variants
• New formulations for two location problems with interconnected facilities
• Three network design problems for community energy storage
• SDP-based Benders decomposition for solving p-median quadratic facility location problems
• Modelling a capacitated location problem for designing multimodal vaccine distribution network using a novel health emergency susceptibility index
• Benders decomposition for the discrete ordered median problem
• Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the \(\mathrm{p}\)-median problem
• A resonance neural network for the k-median problem

This page was built for publication: An efficient Benders decomposition for the \(p\)-median problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167396)