Discrete facility location in machine learning

I. L. Vasilyev ; A. V. Ushakov

Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 4, pp. 5-60.

Résumé

Facility location problems form a wide class of optimization problems, extremely popular in combinatorial optimization and operations research. In any facility location problem, one must locate a set of facilities in order to satisfy the demands of customers so as a certain objective function is optimized. Besides numerous applications in public and private sectors, the problems are widely used in machine learning. For example, clustering can be viewed as a facility location problem where one needs to partition a set of customers into clusters assigned to open facilities. In this survey we briefly look at how ideas and approaches arisen in the field of facility location led to modern, popular machine learning algorithms supported by many data mining and machine learning software packages. We also review the state-of-the-art exact methods and heuristics, as well as some extensions of basic problems and algorithms arisen in applied machine learning tasks. Note that the main emphasis here lies on discrete facility location problems, which, for example, underlie many widely used clustering algorithms (PAM, affinity propagation, etc.). Since the high computational complexity of conventional facility location-based clustering algorithms hinders their application to modern large-scale real-life datasets, we also survey some modern approaches to implementation of the algorithms for such large data collections. Bibliogr. 138.

Détail

Keywords: machine learning, facility location, clustering.

Bibliographie

[1] Cooper L., “Location-allocation problems”, Oper. Res., 11:3 (1963), 331–343 | DOI | Zbl

[2] Cooper L., “Heuristic methods for location-allocation problems”, SIAM Rev., 6:1 (1964), 37–53 | DOI | Zbl

[3] Plastria F., “The Weiszfeld algorithm: Proof, amendments, and extensions”, Foundations of Location Analysis, Springer, New York, 2011, 357–389 | DOI | Zbl

[4] Lloyd S., “Least squares quantization in PCM”, IEEE Trans. Inf. Theory, 28:2 (1982), 129–137 | DOI | Zbl

[5] Forgy E. W., “Cluster analysis of multivariate data: Efficiency versus interpretability of classifications”, Biometrics, 21:3 (1965), 768–769

[6] Banerjee A., Merugu S., Dhillon I. S., Ghosh J., “Clustering with Bregman divergences”, J. Mach. Learn. Res., 6:58 (2005), 1705–1749 | Zbl

[7] MacQueen J., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Stat. Probab. (Berkeley, USA, June 21–July 18, 1965; Dec. 27, 1965–Jan. 7, 1966), v. 1, Univ. California Press, Berkeley, 1967, 281–297 | Zbl

[8] Vinod H. D., “Integer programming and the theory of grouping”, J. Am. Stat. Assoc., 64:326 (1969), 506–519 | DOI | Zbl

[9] Balinski M. L., “Integer programming: Methods, uses, computations”, Manage. Sci., 12:3 (1965), 253–313 | DOI | Zbl

[10] Efroymson M. A., Ray T. L., “A branch-bound algorithm for plant location”, Oper. Res., 14:3 (1966), 361–368 | DOI

[11] ReVelle C. S., Swain R. W., “Central facilities location”, Geogr. Anal., 2:1 (1970), 30–42 | DOI

[12] Hakimi S. L., “Optimal location of switching centers and the absolute centers and medians of a graph”, Oper. Res., 12:3 (1964), 450–459 | DOI | Zbl

[13] Hakimi S. L., “Optimum distribution of switching centers in a communication network and some related graph theoretic problems”, Oper. Res., 13:3 (1965), 462–475 | DOI | Zbl

[14] Kaufman L., Rousseeuw P. J., “Clustering by means of medoids”, Statistical Data Analysis Based on the $L_1$-Norm and Related Methods, North-Holland, Amsterdam, 1987, 405–416

[15] Charikar M., Guha S., Tardos E., Shmoys D. B., “A constant-factor approximation algorithm for the $k$-median problem”, J. Comput. Syst. Sci., 65:1 (2002), 129–149 | DOI | Zbl

[16] Balcan M.-F., Blum A., Gupta A., “Approximate clustering without the approximation”, Proc. 20th Annu. ACM-SIAM Symp. Discrete Algorithms (New York, USA, Jan. 4–6, 2009), SIAM, Philadelphia, 2009, 1068–1077 | DOI | Zbl

[17] Ahmadian S., Norouzi-Fard A., Svensson O., Ward J., “Better guarantees for $k$-means and Euclidean $k$-median by primal-dual algorithms”, SIAM J. Comput., 49:4 (2020), FOCS17-97–FOCS17-156 | DOI | Zbl

[18] Kariv O., Hakimi S., “An algorithmic approach to network location problems. II: The $p$-medians”, SIAM J. Appl. Math., 37:3 (1979), 539–560 | DOI | Zbl

[19] Megiddo N., Supowit K. J., “On the complexity of some common geometric location problems”, SIAM J. Comput., 13:1 (1984), 182–196 | DOI | Zbl

[20] Mahajan M., Nimbhorkar P., Varadarajan K., “The planar $k$-means problem is NP-hard”, Theor. Comput. Sci., 442 (2012), 13–21 | DOI | Zbl

[21] Megiddo N., Zemel E., Hakimi S. L., “The maximum coverage location problem”, SIAM J. Algebr. Discrete Methods, 4:2 (1983), 253–261 | DOI | Zbl

[22] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Mach. Learn., 75:2 (2009), 245–248 | DOI | Zbl

[23] Papadimitriou C. H., “Worst-case and probabilistic analysis of a geometric location problem”, SIAM J. Comput., 10:3 (1981), 542–557 | DOI | Zbl

[24] Rosing K. E., ReVelle C. S., Rosing-Vogelaar H., “The $p$-median and its linear programming relaxation: An approach to large problems”, J. Oper. Res. Soc., 30:9 (1979), 815–823 | DOI | Zbl

[25] Church R. L., “COBRA: A new formulation of the classic $p$-median location problem”, Ann. Oper. Res., 122:1–4 (2003), 103–120 | DOI | Zbl

[26] Cornuejols G., Nemhauser G. L., Wolsey L. A., “A canonical representation of simple plant location problems and its applications”, SIAM J. Algebr. Discrete Methods, 1:3 (1980), 261–272 | DOI | Zbl

[27] Hansen P., Brimberg J., Urosević D., Mladenović N., “Solving large $p$-median clustering problems by primal-dual variable neighborhood search”, Data Min. Knowl. Discov., 19:3 (2009), 351–375 | DOI

[28] Elloumi S., “A tighter formulation of the $p$-median problem”, J. Comb. Optim., 19:1 (2010), 69–83 | DOI | Zbl

[29] Maranzana F. E., “On the location of supply points to minimize transport costs”, Oper. Res. Q, 15:3 (1964), 261–270 | DOI

[30] Teitz M. B., Bart P., “Heuristic methods for estimating the generalized vertex median of a weighted graph”, Oper. Res., 16:5 (1968), 955–961 | DOI | Zbl

[31] Hartigan J. A., Wong M. A., “Algorithm AS 136: A $k$-means clustering algorithm”, J. R. Stat. Soc. Ser. C, 28:1 (1979), 100–108 | Zbl

[32] Church R. L., ReVelle C. S., “Theoretical and computational links between the $p$-median, location set-covering, and the maximal covering location problem”, Geogr. Anal., 8:4 (1976), 406–415 | DOI

[33] Cornuejols G., Fisher M. L., Nemhauser G. L., “Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms”, Manage. Sci., 23:8 (1977), 789–810 | DOI | Zbl

[34] Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V., “Local search heuristics for $k$-median and facility location problems”, SIAM J. Comput., 33:3 (2004), 544–562 | DOI | Zbl

[35] Gupta A., Tangwongsan K., Simpler analyses of local search algorithms for facility location, Cornell Univ., Ithaca, NY, 2008, arXiv: 0809.2554

[36] Yu. A. Kochetov, M. G. Pashchenko, A. V. Plyasunov, “On the complexity of local search in the $p$-median problem”, Diskretn. Anal. Issled. Oper., Ser. 2, 12:2 (2005), 44–71 (Russian) | Zbl

[37] Alekseeva E. V., Kochetov Yu. A., Plyasunov A. V., “Complexity of local search for the $p$-median problem”, Eur. J. Oper. Res., 191:3 (2008), 736–752 | DOI | Zbl

[38] Whitaker R. A., “A fast algorithm for the greedy interchange for large-scale clustering and median location problems”, INFOR, 21 (1983), 95–108 | Zbl

[39] Whitaker R. A., “Some interchange algorithms for median location problems”, Environ. Plann. Ser. B, 9:2 (1982), 119–129 | DOI

[40] Densham P. J., Rushton G., “A more efficient heuristic for solving large $p$-median problems”, Pap. Reg. Sci., 71:3 (1992), 307–329 | DOI

[41] Hansen P., Mladenović N., “Variable neighborhood search for the $p$-median”, Locat. Sci., 5:4 (1997), 207–226 | DOI | Zbl

[42] Schubert E., Rousseeuw P. J., “Faster $k$-medoids clustering: Improving the PAM, CLARA, and CLARANS algorithms”, Similarity Search and Applications, Proc. 12th Int. Conf. (Newark, USA, Oct. 2–4, 2019), Lect. Notes Comput. Sci., 11807, Springer, Cham, 2019, 171–187 | DOI

[43] Resende M. G. C., Werneck R. F., “A fast swap-based local search procedure for location problems”, Ann. Oper. Res., 150:1 (2007), 205–230 | DOI | Zbl

[44] Feo T. A., Resende M. G. C., “Greedy randomized adaptive search procedures”, J. Glob. Optim., 6:2 (1995), 109–133 | DOI | Zbl

[45] Resende M. G. C., Werneck R. F., “A hybrid heuristic for the $p$-median problem”, J. Heuristics, 10:1 (2004), 59–88 | DOI | Zbl

[46] Mirzasoleiman B., Badanidiyuru A., Karbasi A., Vondrák J., Krause A., “Lazier than lazy greedy”, Proc. 29th AAAI Conf. Artificial Intelligence (Austin, USA, Jan. 25–30, 2015), AAAI Press, Palo Alto, 2015, 1812–1818

[47] Tiwari M., Zhang M. J., Mayclin J., Thrun S., “Bandit-PAM: Almost linear time $k$-medoids clustering via multi-armed bandits”, Proc. 34th Conf. Neural Information Processing Systems (Vancouver, Canada, Dec. 6–12, 2020), Curran Assoc., Red Hook, 2020, 10211–10222

[48] Hastie T., Tibshirani R., Friedman J., The elements of statistical learning: Data mining, inference, and prediction, Springer, New York, 2009 | Zbl

[49] Park H.-S., Jun C.-H., “A simple and fast algorithm for $k$-medoids clustering”, Expert Syst. Appl., 36:2-2 (2009), 3336–3341 | DOI

[50] Newling J., Fleuret F., “A sub-quadratic exact medoid algorithm”, Proc. Mach. Learn. Res., 54 (2017), 185–193

[51] Bagaria V., Kamath G., Ntranos V., Zhang M., Tse D., “Medoids in almost-linear time via multi-armed bandits”, Proc. Mach. Learn. Res., 84 (2018), 500–509

[52] Paterlini A. A., Nascimento M. A., Jr. C. T., “Using pivots to speed-up $k$-medoids clustering”, J. Inf. Data Manage, 2:2 (2011), 221–236

[53] Kaufman L., Rousseeuw P. J., Finding groups in data: An introduction to cluster analysis, Wiley, Hoboken, NJ, 2005

[54] Ng R. T., Han J., “CLARANS: A method for clustering objects for spatial data mining”, IEEE Trans. Knowl. Data Eng., 14:5 (2002), 1003–1016 | DOI

[55] Newling J., Fleuret F., “$K$-medoids for $K$-means seeding”, Proc. 31st Int. Conf. Neural Information Processing Systems (Long Beach, CA, USA, Dec. 4–9, 2017), Curran Assoc., Red Hook, NY, 2017, 5201–5209

[56] Van der Laan M., Pollard K., Bryan J., “A new partitioning around medoids algorithm”, J. Stat. Comput. Simul., 73:8 (2003), 575–584 | DOI | Zbl

[57] Zhang Q., Couloigner I., “A new and efficient $k$-medoid algorithm for spatial clustering”, Computational Science and Its Applications, Proc. Int. Conf. (Singapore, May 9–12, 2005), v. 3, Lect. Notes Comput. Sci., 3482, Springer, Heidelberg, 2005, 181–189 | DOI

[58] Yu D., Liu G., Guo M., Liu X., “An improved $k$-medoids algorithm based on step increasing and optimizing medoids”, Expert Syst. Appl., 92 (2018), 464–473 | DOI

[59] Wang X., Wang X., Wilkes D. M., Machine learning-based natural scene recognition for mobile robot localization in an unknown environment, Springer, Singapore, 2020, 85–108 | DOI

[60] Zadegan S. M. R., Mirzaie M., Sadoughi F., “Ranked $k$-medoids: A fast and accurate rank-based partitioning algorithm for clustering large datasets”, Knowl.-Based Syst., 39 (2013), 133–143 | DOI

[61] Rangel E. M., Hendrix W., Agrawal A., Liao W., Choudhary A., “AGORAS: A fast algorithm for estimating medoids in large datasets”, Procedia Comput. Sci., 80 (2016), 1159–1169 | DOI

[62] Fushimi T., Saito K., Ikeda T., Kazama K., “Accelerating greedy $k$-medoids clustering algorithm with $L_1$ distance by pivot generation”, Foundations of Intelligent Systems, Proc. 23rd Int. Symp. (Warsaw, Poland, June 26–29, 2017), Lect. Notes Comput. Sci., 10352, Springer, Cham, 2017, 87–96 | DOI

[63] An H.-C., Svensson O., “Recent developments in approximation algorithms for facility location and clustering problems”, Combinatorial Optimization and Graph Algorithms, Springer, Singapore, 2017, 1–19 | Zbl

[64] Mladenović N., Brimberg J., Hansen P., Moreno-Pérez J., “The $p$-median problem: A survey of metaheuristic approaches”, Eur. J. Oper. Res., 179:3 (2007), 927–939 | DOI | Zbl

[65] Reese J., “Solution methods for the $p$-median problem: An annotated bibliography”, Networks, 28:3 (2006), 125–142 | DOI

[66] Avella P., Sassano A., Vasilyev I. L., “Computational study of large-scale $p$-median problems”, Math. Program., 109:1 (2007), 89–114 | DOI | Zbl

[67] Church R. L., “BEAMR: An exact and approximate model for the $p$-median problem”, Comput. Oper. Res., 35:2 (2008), 417–426 | DOI | Zbl

[68] García S., Labbé M., Marín A., “Solving large $p$-median problems with a radius formulation”, INFORMS J. Comput., 23:4 (2011), 546–556 | DOI | Zbl

[69] Mulvey J. M., Crowder H. P., “Cluster analysis: An application of Lagrangian relaxation”, Manage. Sci., 25:4 (1979), 329–340 | DOI | Zbl

[70] Geoffrion A. M., “Lagrangian relaxation for integer programming”, Approaches to Integer Programming, Math. Program. Study, 2, Springer, Heidelberg, 1974, 82–114 | DOI

[71] Beltran C., Tadonki C., Vial J., “Solving the $p$-median problem with a semi-Lagrangian relaxation”, Comput. Optim. Appl., 35:2 (2006), 239–260 | DOI | Zbl

[72] Avella P., Boccia M., Salerno S., Vasilyev I. L., “An aggregation heuristic for large scale $p$-median problem”, Comput. Oper. Res., 39:7 (2012), 1625–1632 | DOI | Zbl

[73] Irawan C. A., Salhi S., “Solving large $p$-median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search”, J. Glob. Optim., 63 (2015), 537–554 | DOI | Zbl

[74] Cebecauer M., Buzna L., “A versatile adaptive aggregation framework for spatially large discrete location-allocation problems”, Comput. Ind. Eng., 111 (2017), 364–380 | DOI

[75] Jain K., Vazirani V. V., “Approximation algorithms for metric facility location and $k$-median problems using the primal-dual schema and Lagrangian relaxation”, J. ACM, 48:2 (2001), 274–296 | DOI | Zbl

[76] Li S., Svensson O., “Approximating $k$-median via pseudo-approximation”, Proc. 45th Annu. ACM Symp. Theory of Computing (Palo Alto, USA, June 1–4, 2013), ACM, New York, 2013, 901–910 | Zbl

[77] Byrka J., Pensyl T., Rybicki B., Srinivasan A., Trinh K., “An improved approximation for $k$-median and positive correlation in budgeted optimization”, ACM Trans. Algorithms, 13:2 (2017), 23, 31 pp. | DOI | Zbl

[78] Jain K., Mahdian M., Markakis E., Saberi A., Vazirani V. V., “Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP”, J. ACM, 50:6 (2003), 795–824 | DOI | Zbl

[79] Nellore A., Ward R., “Recovery guarantees for exemplar-based clustering”, Inf. Comput., 245 (2015), 165–180 | DOI | Zbl

[80] Awasthi P., Bandeira A. S., Charikar M., Krishnaswamy R., Villar S., Ward R., “Relax, no need to round: Integrality of clustering formulations”, Proc. 2015 Conf. Innovations in Theoretical Computer Science (Rehovot, Israel, Jan. 11–13, 2015), ACM, New York, 2015, 191–200 | DOI | Zbl

[81] Crainic T. G., Gendreau M., Hansen P., Mladenović N., “Cooperative parallel variable neighborhood search for the $p$-median”, J. Heuristics, 10:3 (2004), 293–314 | DOI

[82] Garcia-López F., Melián-Batista B., Moreno-Pérez J. A., Moreno-Vega J. M., “The parallel variable neighborhood search for the $p$-median problem”, J. Heuristics, 8:3 (2002), 375–388 | DOI | Zbl

[83] Garcia-López F., Melián-Batista B., Moreno-Pérez J. A., Moreno-Vega J. M., “Parallelization of the scatter search for the $p$-median problem”, Parallel Comput., 29:5 (2003), 575–589 | DOI

[84] Crainic T. G., Toulouse M., “Parallel meta-heuristics”, Handbook of Metaheuristics, Int. Ser. Oper. Res. Manage. Sci., 146, Springer, New York, 2010, 497–541

[85] Ma L., Lim G. J., “GPU-based parallel vertex substitution algorithm for the $p$-median problem”, Comput. Ind. Eng., 64:1 (2013), 381–388 | DOI

[86] Xiao N., “A parallel cooperative hybridization approach to the $p$-median problem”, Environ. Plann. Ser. B, 39:4 (2012), 755–774 | DOI

[87] Arbelaez A., Quesada L., “Parallelising the $k$-medoids clustering problem using space-partitioning”, Proc. 6th Annu. Symp. Combinatorial Search (Leavenworth, USA, July 11–13, 2013), AAAI, Palo Alto, 2013, 20–28

[88] Blelloch G. E., Tangwongsan K., “Parallel approximation algorithms for facility-location problems”, Proc. 22nd Annu. ACM Symp. Parallelism in Algorithms and Architectures (Thira Santorini, Greece, June 13–15, 2010), ACM, New York, 2010, 315–324

[89] Blelloch G. E., Gupta A., Tangwongsan K., “Parallel probabilistic tree embeddings, $k$-median, and buy-at-bulk network design”, Proc. 24th Annu. ACM Symp. Parallelism in Algorithms and Architectures (Pittsburgh, USA, June 25–27, 2012), ACM, New York, 2012, 205–213

[90] Bandyapadhyay S., Inamdar T., Pai S., Pemmaraju S. V., “Near-optimal clustering in the $k$-machine model”, Proc. 19th Int. Conf. Distributed Computing and Networking (Varanasi, India, Jan. 4–7, 2018), ACM, New York, 2018, 15, 10 pp.

[91] Karloff H. J., Suri S., Vassilvitskii S., “A model of computation for MapReduce”, Proc. 21st Annu. ACM-SIAM Symp. Discrete Algorithms (Austin, USA, Jan. 17-19, 2010), SIAM, Philadelphia, PA, 2010, 938–948 | DOI | Zbl

[92] Ene A., Im S., Moseley B., “Fast clustering using MapReduce”, Proc. 17th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (San Diego, USA, Aug. 21–24, 2011), ACM, New York, 2011, 681–689

[93] Jakovits P., Srirama S. N., “Clustering on the cloud: Reducing CLARA to MapReduce”, Proc. 2nd Nordic Symp. Cloud Computing and Internet Technologies (Oslo, Norway, Sep. 2–3, 2013), ACM, New York, 2013, 64–71 | DOI

[94] Ushakov A. V., Vasilyev I. L., “Near-optimal large-scale $k$-medoids clustering”, Inf. Sci., 545 (2021), 344–362 | DOI | Zbl

[95] Yang X., Lian L., “A New data mining algorithm based on MapReduce and Hadoop”, Int. J. Signal Process., Image Process., Pattern Recognit., 7:2 (2014), 131–142

[96] Martino A., Rizzi A., Frattale Mascioli F. M., “Efficient approaches for solving the large-scale $k$-medoids problem: Towards structured data”, Computational Intelligence, Proc. 9th Int. Joint Conf. (Funchal-Madeira, Portugal, Nov. 1–3, 2017), Springer, Cham, 2019, 199–219 | DOI

[97] Zhu Y., Wang F., Shan X., Lv X., “$K$-medoids clustering based on MapReduce and optimal search of medoids”, Proc. 9th Int. Conf. Comput. Sci. Education (Vancouver, Canada, Aug 22–24, 2014), IEEE, Piscataway, 2014, 573–577

[98] Song H., Lee J.-G., Han W.-S., “PAMAE: Parallel $k$-medoids clustering with high accuracy and efficiency”, Proc. 23rd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (Halifax, Canada, Aug. 13–17, 2017), ACM, New York, 2017, 1087–1096 | DOI

[99] Mirzasoleiman B., Karbasi A., Sarkar R., Krause A., “Distributed submodular maximization: Identifying representative elements in massive data”, Proc. 26th Int. Conf. Neural Information Processing Systems (Lake Tahoe, USA, Dec. 5–10, 2013), v. 2, Curran Assoc., Red Hook, NY, 2013, 2049–2057

[100] Redondo J. L., Marín A., Ortigosa P. M., “A parallelized Lagrangian relaxation approach for the discrete ordered median problem”, Ann. Oper. Res., 246:1 (2016), 253–272 | DOI | Zbl

[101] Mancini E. P., Marcarelli S., Vasilyev I. L., Villano U., “A grid-aware MIP solver: Implementation and case studies”, Futur. Gener. Comp. Syst., 24:2 (2008), 133–41 | DOI

[102] Lai P.-S., Fu H.-C., “Variance enhanced $k$-medoid clustering”, Expert Syst. Appl., 38:1 (2011), 764–775 | DOI

[103] Ayyala D. N., Lin S., “GrammR: Graphical representation and modeling of count data with application in metagenomics”, Bioinformatics, 31:10 (2015), 1648–1654 | DOI

[104] Elhamifar E., Sapiro G., Vidal R., “Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery”, Proc. 25th Int. Conf. Neural Information Processing Systems (Lake Tahoe, USA, Dec. 3–8, 2012), v. 1, Curran Assoc., Red Hook, NY, 2012, 19–27

[105] Charikar M., Khuller S., Mount D. M., Narasimhan G., “Algorithms for facility location problems with outliers”, Proc. 12th Annu. ACM-SIAM Symp. Discrete Algorithms (Washington, USA, Jan. 7–9, 2001), SIAM, Philadelphia, PA, 2001, 642–651 | Zbl

[106] Frey B. J., Dueck D., “Clustering by passing messages between data points”, Science, 315:5814 (2007), 972–976 | DOI | Zbl

[107] Brusco M. J., Köhn H.-F., “Comment on “Clustering by passing messages between data points””, Science, 319:5864 (2008), 726–726 | DOI

[108] Brusco M. J., Steinley D., “Affinity propagation and uncapacitated facility location problems”, J. Classif., 32:3 (2015), 443–480 | DOI | Zbl

[109] Leone M., Sumedha, Weigt M., “Clustering by soft-constraint affinity propagation: Applications to gene-expression data”, Bioinformatics, 23:20 (2007), 2708–2715 | DOI

[110] Mirchandani P., Jagannathan R., “Discrete facility location with nonlinear diseconomies in fixed costs”, Ann. Oper. Res., 18:1 (1989), 213–224 | DOI | Zbl

[111] Körkel M., “Discrete facility location with nonlinear facility costs”, RAIRO-Oper. Res., 25:1 (1991), 31–43 | DOI | Zbl

[112] Carrizosa E., Ushakov A. V., Vasilyev I. L., “A computational study of a nonlinear minsum facility location problem”, Comput. Oper. Res., 39:11 (2012), 2625–2633 | DOI | Zbl

[113] Aghaee A., Ghadiri M., Baghshah M. S., “Active distance-based clustering using $k$-medoids”, Advances in Knowledge Discovery and Data Mining, Proc. 20th Pacific-Asia Conf. (Auckland, New Zealand, Apr. 19–22, 2016), Lect. Notes Comput. Sci., 9651, Springer, Cham, 2016, 253–264 | DOI

[114] Randel R., Aloise D., Mladenović N., Hansen P., “On the $k$-medoids model for semi-supervised clustering”, Variable Neighborhood Search, Proc. 6th Int. Conf. (Sithonia, Greece, Oct. 4–7, 2018), Lect. Notes Comput. Sci., 11328, Springer, Cham, 2019, 13–27 | DOI

[115] Marín A., Pelegrín M., “Adding incompatibilities to the simple plant location problem: Formulation, facets and computational experience”, Comput. Oper. Res., 104 (2019), 174–190 | DOI | Zbl

[116] Marín A., Pelegrín M., “The double-assignment plant location problem with co-location”, Comput. Oper. Res., 126 (2021), 105059 | DOI | Zbl

[117] Fersini E., Messina E., Archetti F., “A $p$-median approach for predicting drug response in tumour cells”, BMC Bioinform, 15:1 (2014), 1–19 | DOI

[118] Ushakov A. V., Klimentova K. B., Vasilyev I. L., “Bi-level and bi-objective $p$-median type problems for integrative clustering: Application to analysis of cancer gene-expression and drug-response data”, IEEE-ACM Trans. Comput. Biol. Bioinform., 15:1 (2018), 46–59 | DOI

[119] E. A. Alekseeva, Yu. A. Kochetov, “Genetic local search for the $p$-median problem with customer preferences”, Diskretn. Anal. Issled. Oper., Ser. 2, 14:1 (2007), 3–31 (Russian) | Zbl

[120] Cánovas L., García S., Labbé M., Marín A., “A strengthened formulation for the simple plant location problem with order”, Oper. Res. Lett., 35:2 (2007), 141–150 | DOI

[121] Vasilyev I. L., Klimentova K. B., Boccia M., “Polyhedral study of simple plant location problem with order”, Oper. Res. Lett., 41:2 (2013), 153–158 | DOI | Zbl

[122] I. L. Vasilyev, K. B. Klimentova, “A branch and bound method for the facility location problem with customer preferences”, J. Appl. Ind. Math., 4:3 (2010), 441–454 | DOI

[123] Benati S., García S., “A mixed integer linear model for clustering with variable selection”, Comput. Oper. Res., 43 (2014), 280–285 | DOI | Zbl

[124] Benati S., García S., Puerto J., “Mixed integer linear programming and heuristic methods for feature selection in clustering”, J. Oper. Res. Soc., 69:9 (2018), 1379–1395 | DOI

[125] Kuehn A. A., Hamburger M. J., “A heuristic program for locating warehouses”, Manage. Sci., 9:4 (1963), 643–666 | DOI

[126] Mulvey J. M., Beck M. P., “Solving capacitated clustering problems”, Eur. J. Oper. Res., 18:3 (2003), 339–348 | DOI

[127] Negreiros M., Palhano A., “The capacitated centred clustering problem”, Comput. Oper. Res., 33:6 (2006), 1639–1663 | DOI | Zbl

[128] Boccia M., Sforza A., Sterle C., Vasilyev I. L., “A cut and branch approach for the capacitated $p$-median problem based on Fenchel cutting planes”, J. Math. Model. Algorithms, 7 (2008), 43–58 | DOI | Zbl

[129] Gnägi M., Baumann P., “A matheuristic for large-scale capacitated clustering”, Comput. Oper. Res., 132 (2021), 105304 | DOI

[130] Lorena L. A. N., Senne E. L. F., “A column generation approach to capacitated $p$-median problems”, Comput. Oper. Res., 31:6 (2004), 863–876 | DOI | Zbl

[131] Mai F., Fry M. J., Ohlmann J. W., “Model-based capacitated clustering with posterior regularization”, Eur. J. Oper. Res., 271:2 (2018), 594–605 | DOI | Zbl

[132] Stefanello F., de Araújo O. C. B., Müller F. M., “Matheuristics for the capacitated $p$-median problem”, Int. Trans. Oper. Res., 22:1 (2015), 149–167 | DOI | Zbl

[133] Chou C.-A., Chaovalitwongse W. A., Berger-Wolf T. Y., DasGupta B., Ashley M. V., “Capacitated clustering problem in computational biology: Combinatorial and statistical approach for sibling reconstruction”, Comput. Oper. Res., 39:3 (2012), 609–619 | DOI | Zbl

[134] Frahm J.-M., Fite-Georgel P., Gallup D. et al., “Building Rome on a cloudless day”, Computer Vision, Proc. 11th Eur. Conf. (Heraklion, Greece, Sep. 5–11, 2010), v. 4, Lect. Notes Comput. Sci., 6314, Springer, Heidelberg, 2010, 368–381 | DOI

[135] Gong Y., Pawlowski M., Yang F., Brandy L., Boundev L., Fergus R., “Web scale photo hash clustering on a single machine”, Proc. 2015 IEEE Conf. Computer Vision and Pattern Recognition (Boston, USA, June 7–12, 2015), IEEE, Piscataway, 2015, 19–27 | DOI

[136] Brusco M. J., Steinley D., Stevens J., “$K$-medoids inverse regression”, Commun. Stat. Theory Methods, 48:20 (2019), 4999–5011 | DOI

[137] Suárez J. L., García S., Herrera F., “A tutorial on distance metric learning: Mathematical foundations, algorithms, experimental analysis, prospects and challenges”, Neurocomputing, 425 (2021), 300–322 | DOI

[138] Song H. O., Jegelka S., Rathod V., Murphy K., “Deep metric learning via facility location”, Proc. 2017 IEEE Conf. Computer Vision and Pattern Recognition (Honolulu, USA, July 21–26, 2017), IEEE, Piscataway, 2017, 2206–2214 | DOI