Two exact algorithms for the capacitated \(p\)-median problem (Q1421050)

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.