Two exact algorithms for the capacitated \(p\)-median problem
type: Item
instance of: scholarly article
title: Two exact algorithms for the capacitated \(p\)-median problem
zbMATH Open document ID: 1109.90054
author: Alberto Ceselli
published in: 4OR
publication date: 2004-02-19T00:00:00Z
review text: The problem of partitioning the node set of a graph into \(p\) subsets and selecting a median node for every subset such that the sum of the distances between each node and its median is minimized, is called the \(p\)-median problem (PMP). If one defines a production capacity for each candidate median and a demand for each user and if one imposes that the sum of the demands assigned to the same facility cannot exceed its capacity, one obtains the capacitated \(p\)-median problem (CPMP). In this paper, 2 exact methods for the solution of (CPMP) are proposed: first, a branch and bound algorithm that uses Lagrangean relaxation and subgradient optimisation to compute dual bounds; second, a branch and price algorithm in which dual bounds are obtained by solving (by column generation) the linear relaxation of the CPMP reformulation as a set partitioning problem with side constraints. Related column pool management policies are analysed, and an adaptation of the MINKNAP algorithm of Pisinger (1995) for the solution of knapsack problems is discussed that may arise as subproblems in both methods. Finally, the performance of the two methods are compared with that of the standard MIP-solver CPLEX 6.5.3.
reviewed by: Reinhardt Euler
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 2032488
zbMATH Keywords: location theory
zbMATH Keywords: Lagrangean relaxation
zbMATH Keywords: column generation
zbMATH Keywords: branch and bound
describes a project that uses: CPLEX
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2032488