IDEAS home Printed from https://ideas.repec.org/a/spr/jclass/v32y2015i3p443-480.html
   My bibliography  Save this article

Affinity Propagation and Uncapacitated Facility Location Problems

Author

Listed:
  • Michael Brusco

    ()

  • Douglas Steinley

    ()

Abstract

One of the most important distinctions that must be made in clustering research is the difference between models (or problems) and the methods for solving those problems. Nowhere is this more evident than with the evaluation of the popular affinity propagation algorithm (apcluster.m), which is a MATLAB implementation of a neural clustering method that has received significant attention in the biological sciences and other disciplines. Several authors have undertaken comparisons of apcluster.m with methods designed for models that fall within the class of uncapacitated facility location problems (UFLPs). These comparative models include the p-center (or K-center) model and, more importantly, the p-median (or K-median) model. The results across studies are conflicting and clouded by the fact that, although similar, the optimization model underlying apcluster.m is slightly different from the p-median model and appreciably different from the pcenter model. In this paper, we clarify that apcluster.m is actually a heuristic for a ‘maximization version’ of another model in the class of UFLPs, which is known as the simple plant location problem (SPLP). An exact method for the SPLP is described, and the apcluster.m program is compared to a fast heuristic procedure (sasplp.m) in both a simulation experiment and across numerous datasets from the literature. Although the exact method is the preferred approach when computationally feasible, both apcluster.m and sasplp.m are efficient and effective heuristic approaches, with the latter slightly outperforming the former in most instances. Copyright Classification Society of North America 2015

Suggested Citation

  • Michael Brusco & Douglas Steinley, 2015. "Affinity Propagation and Uncapacitated Facility Location Problems," Journal of Classification, Springer;The Classification Society, vol. 32(3), pages 443-480, October.
  • Handle: RePEc:spr:jclass:v:32:y:2015:i:3:p:443-480
    DOI: 10.1007/s00357-015-9187-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00357-015-9187-x
    Download Restriction: Access to full text is restricted to subscribers.

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alfred A. Kuehn & Michael J. Hamburger, 1963. "A Heuristic Program for Locating Warehouses," Management Science, INFORMS, vol. 9(4), pages 643-666, July.
    2. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    3. Douglas Steinley & Robert Henson, 2005. "OCLUS: An Analytic Method for Generating Clusters with Known Overlap," Journal of Classification, Springer;The Classification Society, vol. 22(2), pages 221-250, September.
    4. 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.
    5. Glenn Milligan & Martha Cooper, 1985. "An examination of procedures for determining the number of clusters in a data set," Psychometrika, Springer;The Psychometric Society, vol. 50(2), pages 159-179, June.
    6. Douglas Steinley & Michael J. Brusco, 2007. "Initializing K-means Batch Clustering: A Critical Evaluation of Several Techniques," Journal of Classification, Springer;The Classification Society, vol. 24(1), pages 99-121, June.
    7. Hanjoul, Pierre & Peeters, Dominique, 1985. "A comparison of two dual-based procedures for solving the p-median problem," European Journal of Operational Research, Elsevier, vol. 20(3), pages 387-396, June.
    8. Michael Brusco & Hans-Friedrich Köhn, 2009. "Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer;The Psychometric Society, vol. 74(3), pages 457-475, September.
    9. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    10. Simon Blanchard & Daniel Aloise & Wayne DeSarbo, 2012. "The Heterogeneous P-Median Problem for Categorization Based Clustering," Psychometrika, Springer;The Psychometric Society, vol. 77(4), pages 741-762, October.
    11. Christofides, N. & Beasley, J. E., 1982. "A tree search algorithm for the p-median problem," European Journal of Operational Research, Elsevier, vol. 10(2), pages 196-204, June.
    12. Michael Brusco & Douglas Steinley, 2007. "A Comparison of Heuristic Procedures for Minimum Within-Cluster Sums of Squares Partitioning," Psychometrika, Springer;The Psychometric Society, vol. 72(4), pages 583-600, December.
    13. John M. Mulvey & Harlan P. Crowder, 1979. "Cluster Analysis: An Application of Lagrangian Relaxation," Management Science, INFORMS, vol. 25(4), pages 329-340, April.
    14. Lawrence Hubert & Phipps Arabie, 1985. "Comparing partitions," Journal of Classification, Springer;The Classification Society, vol. 2(1), pages 193-218, December.
    15. Glenn Milligan, 1980. "An examination of the effect of six types of error perturbation on fifteen clustering algorithms," Psychometrika, Springer;The Psychometric Society, vol. 45(3), pages 325-342, September.
    16. Michael Brusco & Hans-Friedrich Köhn, 2009. "Erratum to: Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 755-755, December.
    17. A. M. El-Shaieb, 1973. "A New Algorithm for Locating Sources Among Destinations," Management Science, INFORMS, vol. 20(2), pages 221-231, October.
    18. Michael Brusco & J. Cradit, 2001. "A variable-selection heuristic for K-means clustering," Psychometrika, Springer;The Psychometric Society, vol. 66(2), pages 249-270, June.
    19. T. D. Klastorin, 1985. "The p-Median Problem for Cluster Analysis: A Comparative Test Using the Mixture Model Approach," Management Science, INFORMS, vol. 31(1), pages 84-95, January.
    Full references (including those not matched with items on IDEAS)

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jclass:v:32:y:2015:i:3:p:443-480. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla) or (Rebekah McClure). General contact details of provider: http://www.springer.com .

    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 CitEc recognized a reference but did not link an item in RePEc 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 RePEc Author Service 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.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.