Lagrangean duals and exact solution to the capacitated p-center problem

In this work, we address the capacitated p-center problem (CpCP). We study two auxiliary problems, discuss their relation to CpCP, and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly CpCP, based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.