EN|RU
About Journal
Editorial Board

Publishing Ethics
Author Guide Submission
 Prepare Your Manuscript
Peer review
Archive

Volume 28, No 4, 2021, P. 5-60

UDC 519.87
I. L. Vasilyev and A. V. Ushakov
Discrete facility location in machine learning

Abstract:
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.

Keywords: machine learning, facility location, clustering.

DOI: 10.33048/daio.2021.28.714

Igor L. Vasilyev 1
Anton V. Ushakov 1
1. Matrosov Institute for System Dynamics and Control Theory,
134 Lermontov Street, 664033 Irkutsk, Russia
e-mail: vil@icc.ru, aushakov@icc.ru

Received April 30, 2021
Revised June 17, 2021
Accepted June 21, 2021

References

[1] L. Cooper, Location-allocation problems, Oper. Res. 11 (3), 331–343 (1963).

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

[3] F. Plastria, The Weiszfeld algorithm: Proof, amendments, and extensions, in Foundations of Location Analysis (Springer, New York, 2011), pp. 357–389.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[27] P. Hansen, J. Brimberg, D. Urosevic, and N. Mladenovic, Solving large $p$-median clustering problems by primal-dual variable neighborhood search, Data Min. Knowl. Discov. 19 (3), 351–375 (2009).

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

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

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

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

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

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

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

[35] A. Gupta and K. Tangwongsan, Simpler analyses of local search algorithms for facility location (Cornell Univ., Ithaca, NY, 2008) (Cornell Univ. Libr. e-Print Archive; arXiv:0809.2554).

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

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

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

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

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

[41] P. Hansen and N. Mladenovic, Variable neighborhood search for the $p$-median, Locat. Sci. 5 (4), 207–226 (1997).

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

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

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

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

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

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

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

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

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

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

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

[53] L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis (Wiley, Hoboken, NJ, 2005).

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

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

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

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

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

[59] X. Wang, X. Wang, and D. M. Wilkes, Machine Learning-Based Natural Scene Recognition for Mobile Robot Localization in an Unknown Environment (Springer, Singapore, 2020), pp. 85–108.

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

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

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

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

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

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

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

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

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

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

[70] A. M. Geoffrion, Lagrangian relaxation for integer programming, in Approaches to Integer Programming, (Springer, Heidelberg, 1974), pp. 82–114 (Math. Program. Study, Vol. 2).

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

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

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

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

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

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

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

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

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

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

[81] T. G. Crainic, M. Gendreau, P. Hansen, and N. Mladenovic, Cooperative parallel variable neighborhood search for the $p$-median, J. Heuristics 10 (3), 293–314 (2004).

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

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

[84] T. G. Crainic and M. Toulouse, Parallel meta-heuristics, in Handbook of Metaheuristics (Springer, New York, 2010), pp. 497–541 (Int. Ser. Oper. Res. Manage. Sci., Vol. 146).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[106] B. J. Frey and D. Dueck, Clustering by passing messages between data points, Science 315 (5814), 972–976 (2007).

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

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

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

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

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

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

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

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

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

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

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

[118] A. V. Ushakov, K. B. Klimentova, and I. L. Vasilyev, 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), 46–59 (2018).

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

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

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

[122] I. L. Vasilyev and K. B. Klimentova, A branch and bound method for the facility location problem with customer preferences, Diskretn. Anal. Issled. Oper. 16 (2), 21–41 (2009) [Russian] [J. Appl. Ind. Math. 4 (3), 441–454 (2010)].

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

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

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

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

[127] M. Negreiros and A. Palhano, The capacitated centred clustering problem, Comput. Oper. Res. 33 (6), 1639–1663 (2006).

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

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

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

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

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

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

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

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

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

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

[138] H. O. Song, S. Jegelka, V. Rathod, and K. Murphy, Deep metric learning via facility location, in Proc. 2017 IEEE Conf. Computer Vision and Pattern Recognition, Honolulu, USA, July 21–26, 2017 (IEEE, Piscataway, 2017), pp. 2206–2214.
 © Sobolev Institute of Mathematics, 2015