Cluster Analysis: An Application of Lagrangian Relaxation

This paper presents and tests an effective optimization algorithm for clustering homogeneous data. The algorithm iteratively employs a subgradient method for determining lower bounds and a simple search procedure for determining upper bounds. The overall objective is to assign n objects to m mutually exclusive "clusters" such that the sum of the distances from each object to a designated cluster median is minimum. The model represents a special case of the uncapacitated facility location and m-median problems. This technique has proven efficient for examples with n \le 200 (i.e., the number of 0-1 variables \le 40,000); computational experiences with 10 real-world clustering applications are provided. A comparison with a hierarchical agglomerative heuristic, the minimum squared error method, is included. It is shown that the optimization algorithm is an effective solution technique for the homogeneous clustering problem, and also a good method for providing tight lower bounds for evaluating the quality of solutions generated by other procedures.