Cluster Analysis: An Application of Lagrangian Relaxation
AbstractThis 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 25 (1979)
Issue (Month): 4 (April)
cluster analysis; integer programming applications; Lagrangian relaxation; heuristics;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Michael Brusco & Hans-Friedrich Köhn, 2009. "Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer, vol. 74(3), pages 457-475, September.
- Mangiameli, Paul & Chen, Shaw K. & West, David, 1996. "A comparison of SOM neural network and hierarchical clustering methods," European Journal of Operational Research, Elsevier, vol. 93(2), pages 402-417, September.
- Michael Brusco & Douglas Steinley, 2011. "A Tabu-Search Heuristic for Deterministic Two-Mode Blockmodeling of Binary Network Matrices," Psychometrika, Springer, vol. 76(4), pages 612-633, October.
- Maravalle, Maurizio & Simeone, Bruno & Naldini, Rosella, 1997. "Clustering on trees," Computational Statistics & Data Analysis, Elsevier, vol. 24(2), pages 217-234, April.
- Chen, Ja-Shen & Heragu, Sunderesh S., 1999. "Stepwise decomposition approaches for large scale cell formation problems," European Journal of Operational Research, Elsevier, vol. 113(1), pages 64-79, February.
- Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
- Lau, Kin-nam & Leung, Pui-lam & Tse, Ka-kit, 1999. "A mathematical programming approach to clusterwise regression model and its extensions," European Journal of Operational Research, Elsevier, vol. 116(3), pages 640-652, August.
- Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
- Holmberg, Kaj, 1997. "Mean value cross decomposition applied to integer programming problems," European Journal of Operational Research, Elsevier, vol. 97(1), pages 124-138, February.
- Sáez-Aguado, Jesús & Trandafir, Paula Camelia, 2012. "Some heuristic methods for solving p-median problems with a coverage constraint," European Journal of Operational Research, Elsevier, vol. 220(2), pages 320-327.
- D'Alfonso, Thomas H. & Ventura, Jose A., 1995. "Assignment of tools to machines in a flexible manufacturing system," European Journal of Operational Research, Elsevier, vol. 81(1), pages 115-133, February.
- Chen, Mu-Chen & Wu, Hsiao-Pin, 2005. "An association-based clustering approach to order batching considering customer demand patterns," Omega, Elsevier, vol. 33(4), pages 333-343, August.
- Wayne DeSarbo & Vijay Mahajan, 1984. "Constrained classification: The use of a priori information in cluster analysis," Psychometrika, Springer, vol. 49(2), pages 187-215, June.
- Wojtek Krzanowski & Glenn Milligan & Stanley Wasserman & Joseph Galaskiewicz & Joel Levine & Elke Weber & Peter Fishburn & Theodore Crovello & Bernard Baum & Wayne DeSarbo, 1987. "Book reviews," Journal of Classification, Springer, vol. 4(1), pages 111-141, March.
- Stefano Benati & Sergio García, 2012. "A p-median problem with distance selection," Statistics and Econometrics Working Papers ws121913, Universidad Carlos III, Departamento de Estadística y Econometría.
- Lozano, S. & Guerrero, F. & Onieva, L. & Larraneta, J., 1998. "Kohonen maps for solving a class of location-allocation problems," European Journal of Operational Research, Elsevier, vol. 108(1), pages 106-117, July.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.