Cluster Analysis: An Application of Lagrangian Relaxation

Management Science · 1979 · Volume 25 · Issue 4

Abstract

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 ≤ 200 (i.e., the number of 0-1 variables ≤ 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.

Keywords

cluster analysis, integer programming applications, Lagrangian relaxation, heuristics

Enable JavaScript for citation tools and additional paper interactions.