Primal-dual Variable neighborhood search for clustering problems on large networksNenad Mladenovic

LAMIH, University of Valenciennes, France

(joint work with J Brimberg, P Hansen and D Urosevic)

Primal-dual Variable neighborhood search (P-D VNS) is a variant of VNS family where both lower and upper bounds of optimization problem considered are updated during the search for the better solution. In that way, if duality gap is closed, the exact solution can be claimed. In this presentation I will show our implementation P-D VNS in solving large star-clustering problems (known also as p-median) with and without given number of clusters. Computational results are presented on large test instances used in location science, i.e., for entities in 2 dimensional Euclidean space, although our approach is quite general.  For example, we were able to solve exactly instances with 20,000 entities and 20,000 potential cluster centers.