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 ≤ 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.

• 저널Management Science · 25(4) · 329–340
• 토픽Facility Location and Emergency Management · Organizational Behavior and Human Resource Management
• DOI10.1287/mnsc.25.4.329
• 저자John M. Mulvey, Harlan Crowder