{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T12:52:26Z","timestamp":1781614346234,"version":"3.54.5"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T00:00:00Z","timestamp":1760313600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T00:00:00Z","timestamp":1760313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100020619","name":"Universidad Miguel Hern\u00e1ndez","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100020619","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Dendrograms are graphical representations of hierarchical clustering. Different definitions of the distance between two clusters in hierarchical clustering lead to different dendrograms. In this paper we focus on the dendrograms obtained when this distance is assumed to be the maximum of the distances between the elements of one cluster and the elements of the other cluster, known as complete-linkage dendrograms. For initial data where some elements are at the same distance as others, the number of different complete linkage dendrograms, which corresponds to the number of different ways to break ties for equal distances, can be large. We propose a system of linear inequalities whose set of solutions is the entire set of complete linkage dendrograms. Such a system of inequalities allows the inclusion of an objective function to select the best dendrogram among all these dendrograms according to some criteria, which may not be possible with classical dendrogram computation algorithms. We also adapt the system of inequalities to single-linkage dendrograms, where the distance between two clusters is the minimum distance between an element of one cluster and an element of the other cluster. The benefits of describing complete-linkage dendrograms through a system of inequalities are illustrated in a computational study in which five different objective functions are proposed.<\/jats:p>","DOI":"10.1007\/s10479-025-06872-6","type":"journal-article","created":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T10:51:39Z","timestamp":1760352699000},"page":"469-494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Mixed-integer models for complete-linkage clustering"],"prefix":"10.1007","volume":"358","author":[{"given":"Martine","family":"Labb\u00e9","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mercedes","family":"Landete","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7993-3695","authenticated-orcid":false,"given":"Marina","family":"Leal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lorena","family":"N\u00e1cher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,10,13]]},"reference":[{"key":"6872_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s10100-023-00881-1","volume":"32","author":"K \u00c1goston","year":"2024","unstructured":"\u00c1goston, K., & E-Nagy, M. (2024). Mixed integer linear programming formulation for k-means clustering problem. Central European Journal of Operations Research, 32, 11\u201327.","journal-title":"Central European Journal of Operations Research"},{"issue":"2","key":"6872_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1038\/s41591-020-01183-8","volume":"27","author":"F Asnicar","year":"2021","unstructured":"Asnicar, F., Berry, S. E., Valdes, A. M., Nguyen, L. H., Piccinno, G., Drew, D. A., Leeming, E., Gibson, R., Roy, C., Khatib, H. A., et al. (2021). Microbiome connections with host metabolism and habitual diet from 1,098 deeply phenotyped individuals. Nature Medicine, 27(2), 321\u2013332.","journal-title":"Nature Medicine"},{"issue":"4","key":"6872_CR3","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/net.20242","volume":"52","author":"M Ba\u00efou","year":"2008","unstructured":"Ba\u00efou, M., & Barahona, F. (2008). A linear programming approach to increasing the weight of all minimum spanning trees. Networks, 52(4), 227\u2013234.","journal-title":"Networks"},{"key":"6872_CR4","doi-asserted-by":"crossref","unstructured":"Barahona, F. (2006). Network reinforcement. Mathematical Programming,105, 181\u2013200.","DOI":"10.1007\/s10107-005-0648-6"},{"key":"6872_CR5","doi-asserted-by":"publisher","first-page":"130698","DOI":"10.1109\/ACCESS.2021.3114099","volume":"9","author":"A Chhabra","year":"2021","unstructured":"Chhabra, A., Masalkovait\u0117, K., & Mohapatra, P. (2021). An overview of fairness in clustering. IEEE Access, 9, 130698\u2013130720.","journal-title":"IEEE Access"},{"key":"6872_CR6","unstructured":"Chierichetti, F., Kumar, R., Lattanzi S., Vassilvitskii S. (2017). Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30."},{"issue":"1","key":"6872_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.15446\/rce.v44n1.81937","volume":"44","author":"LAB Cruz","year":"2021","unstructured":"Cruz, L. A. B., Lyons, L., & Darghan, E. (2021). Complete-linkage clustering analysis of surrogate measures for road safety assessment in roundabouts. Revista Colombiana de Estad\u00edstica, 44(1), 91\u2013121.","journal-title":"Revista Colombiana de Estad\u00edstica"},{"issue":"2","key":"6872_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.eururo.2020.04.044","volume":"78","author":"L Derosa","year":"2020","unstructured":"Derosa, L., Routy, B., Fidelle, M., Iebba, V., Alla, L., Pasolli, E., Segata, N., Desnoyer, A., Pietrantonio, F., Ferrere, G., et al. (2020). Gut bacteria composition drives primary resistance to cancer immunotherapy in renal cell carcinoma patients. European Urology, 78(2), 195\u2013206.","journal-title":"European Urology"},{"issue":"1","key":"6872_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00357-008-9004-x","volume":"25","author":"A Fern\u00e1ndez","year":"2008","unstructured":"Fern\u00e1ndez, A., & G\u00f3mez, S. (2008). Solving non-uniqueness in agglomerative hierarchical clustering using multidendrograms. Journal of Classification, Springer, 25(1), 43\u201365.","journal-title":"Journal of Classification, Springer"},{"key":"6872_CR10","doi-asserted-by":"crossref","unstructured":"Garc\u00eda, S., Labb\u00e9, M., & Mar\u00edn, A. (2011). Solving large $$p$$-median problems with a radius formulation. INFORMS Journal on Computing, 23(4), 546\u2013556.","DOI":"10.1287\/ijoc.1100.0418"},{"issue":"1","key":"6872_CR11","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1609\/aaai.v27i1.8671","volume":"27","author":"S Gilpin","year":"2013","unstructured":"Gilpin, S., Nijssen, S., & Davidson, I. (2013). Formalizing hierarchical clustering as integer linear programming. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 372\u2013378.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"issue":"7865","key":"6872_CR12","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1038\/s41586-021-03592-2","volume":"595","author":"CD Go","year":"2021","unstructured":"Go, C. D., Knight, J. D., Rajasekharan, A., Rathod, B., Hesketh, G. G., Abe, K. T., Youn, J.-Y., Samavarchi-Tehrani, P., Zhang, H., Zhu, L. Y., et al. (2021). A proximity-dependent biotinylation map of a human cell. Nature, 595(7865), 120\u2013124.","journal-title":"Nature"},{"issue":"1","key":"6872_CR13","first-page":"54","volume":"18","author":"JC Gower","year":"1969","unstructured":"Gower, J. C., & Ross, G. J. (1969). Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1), 54\u201364.","journal-title":"Journal of the Royal Statistical Society: Series C (Applied Statistics)"},{"key":"6872_CR14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF02614317","volume":"79","author":"P Hansen","year":"1997","unstructured":"Hansen, P., & Jaumard, B. (1997). Cluster analysis and mathematical programming. Mathematical Programming, 79, 191\u2013215.","journal-title":"Mathematical Programming"},{"key":"6872_CR15","doi-asserted-by":"crossref","unstructured":"James, G., Witten, D., Hastie, T., Tibshirani, R., et al. (2013).An introduction to statistical learning, vol. 112. Springer.","DOI":"10.1007\/978-1-4614-7138-7"},{"key":"6872_CR16","doi-asserted-by":"crossref","unstructured":"Van Der Kloot, W. A., Spaans, A. M., & Heiser, W. J. Instability of hierarchical cluster analysis due to input order of the data: the permucluster solution. Psychological Methods, 10(4), 468\u2013476.","DOI":"10.1037\/1082-989X.10.4.468"},{"issue":"2","key":"6872_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/j.ejor.2022.11.031","volume":"308","author":"M Labb\u00e9","year":"2023","unstructured":"Labb\u00e9, M., Landete, M., & Leal, M. (2023). Dendrograms, minimum spanning trees and feature selection. European Journal of Operational Research, 308(2), 555\u2013567.","journal-title":"European Journal of Operational Research"},{"key":"6872_CR18","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.cor.2013.07.023","volume":"41","author":"M Landete","year":"2014","unstructured":"Landete, M., & Mar\u00edn, A. (2014). Looking for edge-equitable spanning trees. Computers & Operations Research, 41, 44\u201352.","journal-title":"Computers & Operations Research"},{"issue":"2","key":"6872_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.30812\/varian.v4i2.883","volume":"4","author":"I Muthahharah","year":"2021","unstructured":"Muthahharah, I., & Juhari, A. (2021). A cluster analysis with complete linkage and ward\u2019s method for health service data in Makassar city. Jurnal Varian, 4(2), 109\u2013116.","journal-title":"Jurnal Varian"},{"issue":"4","key":"6872_CR20","doi-asserted-by":"publisher","first-page":"2144","DOI":"10.1287\/ijoc.2022.1166","volume":"34","author":"V Piccialli","year":"2022","unstructured":"Piccialli, V., Sudoso, A., & Wiegele, A. (2022). SOS-SDP: an exact solver for minimum sum-of-squares clustering. INFORMS Journal on Computing, 34(4), 2144\u20132162.","journal-title":"INFORMS Journal on Computing"},{"key":"6872_CR21","doi-asserted-by":"crossref","unstructured":"Segura-Alabart, N., Serratosa, F., G\u00f3mez, S., Fern\u00e1ndez, A.(2022). Nonunique upgma clusterings of microsatellite markers. Briefings in Bioinformatics, 23(5), bbac312.","DOI":"10.1093\/bib\/bbac312"},{"key":"6872_CR22","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00357-022-09419-7","volume":"39","author":"M Vichi","year":"2022","unstructured":"Vichi, M., Cavicchia, C., & Groenen, P. (2022). Hierarchical means clustering. Journal of Classification, 39, 553\u2013577.","journal-title":"Journal of Classification"},{"key":"6872_CR23","doi-asserted-by":"crossref","unstructured":"Willemsen, R., Cavicchia, C., van den Heuvel, W., van de Velden, M.(2025). An exact solution approach for hierarchical clustering. INFORMS Journal on Computing, 0(0)","DOI":"10.1287\/ijoc.2024.0903.cd"},{"key":"6872_CR24","doi-asserted-by":"crossref","unstructured":"Wolsey, L. A. (2020). Integer programming. John Wiley & Sons","DOI":"10.1002\/9781119606475"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06872-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-025-06872-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06872-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T12:00:45Z","timestamp":1781611245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-025-06872-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,13]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["6872"],"URL":"https:\/\/doi.org\/10.1007\/s10479-025-06872-6","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,13]]},"assertion":[{"value":"8 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"All applicable international, national, and\/or institutional guidelines for the care and use of animals were followed. This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"During the preparation of this work the authors used ChatGPT to improve language and readability. After using this tool\/service, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration of generative AI and AI-assisted technologies in the writing process"}}]}}