{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T23:39:33Z","timestamp":1781653173259,"version":"3.54.5"},"reference-count":55,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>In hierarchical clustering, a hierarchy of nested data partitions is obtained. Commonly used agglomerative and divisive heuristics do not optimize over a global objective function. Although several objective functions and approximation algorithms have been proposed, exact methods that find optimal solutions based on these objective functions have received little attention. In this paper, we consider an objective function involving a sum of partitional clustering objectives over each level. We introduce two compact mixed-integer linear programming formulations as well as a set-covering formulation that can handle various objective functions. In addition, we provide a branch-and-price framework to solve the set-covering formulation. We apply our branch-and-price approach to real-world data instances containing up to 200 observations compared with 15 in the literature.<\/jats:p>\n                  <jats:p>History: Accepted by Andrea Lodi, Area Editor for Design &amp; Analysis of Algorithms\u2013Discrete.<\/jats:p>\n                  <jats:p>Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https:\/\/pubsonline.informs.org\/doi\/suppl\/10.1287\/ijoc.2024.0903 ) as well as from the IJOC GitHub software repository ( https:\/\/github.com\/INFORMSJoC\/2024.0903 ). The complete IJOC Software and Data Repository is available at https:\/\/informsjoc.github.io\/ .<\/jats:p>","DOI":"10.1287\/ijoc.2024.0903","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T12:38:26Z","timestamp":1744893506000},"page":"447-462","source":"Crossref","is-referenced-by-count":3,"title":["An Exact Solution Approach for Hierarchical Clustering"],"prefix":"10.1287","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7275-4923","authenticated-orcid":false,"given":"Rick","family":"Willemsen","sequence":"first","affiliation":[{"name":"Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1816-3521","authenticated-orcid":false,"given":"Carlo","family":"Cavicchia","sequence":"additional","affiliation":[{"name":"Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6633-5941","authenticated-orcid":false,"given":"Wilco","family":"van den Heuvel","sequence":"additional","affiliation":[{"name":"Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-9057","authenticated-orcid":false,"given":"Michel","family":"van de Velden","sequence":"additional","affiliation":[{"name":"Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-023-00881-1"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1590\/S0101-74382009000300002"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0349-7"},{"key":"B4","unstructured":"Aloise D, Hansen P, Rocha C (2012b) A column generation algorithm for semi-supervised minimum sum-of-squares clustering. Aloise D, Hansen P, Rocha C, eds.\n                      Proc. Global Optimi. Workshop 2012\n                      , 19\u201322."},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"B6","doi-asserted-by":"crossref","unstructured":"Awasthi P, Bandeira AS, Charikar M, Krishnaswamy R, Villar S, Ward R (2015) Relax, no need to round: Integrality of clustering formulations.\n                      Proc. 2015 Conf. Innovations Theoretical Comput. Sci.\n                      (Association for Computing Machinery, New York), 191\u2013200.","DOI":"10.1145\/2688073.2688116"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0178-5"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/s11336-004-1218-1"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01267-4"},{"key":"B10","first-page":"15065","volume":"33","author":"Chami I","year":"2020","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Charikar M, Chatziafratis V (2017) Approximate hierarchical clustering via sparsest cut and spreading metrics. Klein PN, ed.\n                      Proc. 2017 Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 841\u2013854.","DOI":"10.1137\/1.9781611974782.53"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1145\/3321386"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Dao TBH, Kuo CT, Ravi SS, Vrain C, Davidson I (2018) Descriptive clustering: ILP and CP formulations with applications. Lang J, ed.\n                      Proc. 27th Internat. Joint Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 1263\u20131269.","DOI":"10.24963\/ijcai.2018\/176"},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Dasgupta S (2016) A cost function for similarity-based hierarchical clustering.\n                      Proc. 48th Annual ACM Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 118\u2013127.","DOI":"10.1145\/2897518.2897527"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/0906020"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597328327"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.2307\/2528096"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.05.009"},{"key":"B20","first-page":"372","volume":"27","author":"Gilpin S","year":"2013","journal-title":"27th AAAI Conf. Artificial Intelligence"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0090-6"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01890077"},{"key":"B23","first-page":"2061","author":"Greenberg CS","year":"2021","journal-title":"Proc. 37th Conf. Uncertainty Artificial Intelligence"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00216-2"},{"key":"B25","unstructured":"Hansen P, Jaumard B, Meyer C (2000) A simple enumerative algorithm for unconstrained 0 - 1 quadratic programming. Cahiers du GERAD G-2000-59. https:\/\/numerique.banq.qc.ca\/patrimoine\/details\/52327\/3081864."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s11634-021-00478-z"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1201\/b19706"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.39.6.657"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.6.1034"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224336"},{"key":"B33","unstructured":"MacQueen J (1967) Some methods for classification and analysis of multivariate observations.\n                      Proc. Fifth Berkeley Sympos. Math. Statist. Probab. Vol. 1 Statist.\n                      (University of California Press, Berkeley, CA), 281\u2013297."},{"issue":"1","key":"B34","first-page":"1","volume":"24","author":"Moseley B","year":"2023","journal-title":"J. Machine Learn. Res."},{"key":"B35","doi-asserted-by":"crossref","unstructured":"Mueller M, Kramer S (2010) Integer linear programming models for constrained clustering.\n                      Internat. Conf. Discovery Sci.\n                      (Springer, New York), 159\u2013173.","DOI":"10.1007\/978-3-642-16184-1_12"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i10.17094"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-016-0108-8"},{"key":"B38","first-page":"79","volume":"180","author":"Peng J","year":"2005","journal-title":"Foundations Adv. Data Mining"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105958"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.1166"},{"key":"B41","unstructured":"Rajagopalan A, Vitale F, Vainstein D, Citovsky G, Procopiuc CM, Gentile C (2021) Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees. Meila M, Zhang T, eds.\n                      Proc. 38th Internat. Conf. Machine Learn\n                      ., vol. 139 (PMLR, New York), 8799\u20138809."},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482319"},{"issue":"88","key":"B43","first-page":"1","volume":"18","author":"Roy A","year":"2017","journal-title":"J. Machine Learn. Res."},{"key":"B44","unstructured":"Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed.\n                      Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling\n                      (North-Holland, Amsterdam), 269\u2013280."},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2017.06.053"},{"key":"B46","volume-title":"Combinatorial Optimization","author":"Schrijver A","year":"2003"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2003.11.024"},{"key":"B48","doi-asserted-by":"crossref","unstructured":"Sudoso AM, Aloise D (2024) A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering. Preprint, submitted October 8, https:\/\/arxiv.org\/abs\/2410.06187.","DOI":"10.1287\/ijoc.2024.0938"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1016\/j.dib.2020.105501"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1007\/s00357-022-09419-7"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10500990"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.6099"},{"key":"B53","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. http:\/\/dx.doi.org\/10.1287\/ijoc.2024.0903.cd, https:\/\/github.com\/INFORMSJoC\/2024.0903.","DOI":"10.1287\/ijoc.2024.0903.cd"},{"key":"B54","doi-asserted-by":"crossref","unstructured":"Xia Y, Peng J (2005) A cutting algorithm for the minimum sum-of-squared error clustering.\n                      Proc. SIAM Internat. Data Mining Conf.\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 150\u2013160.","DOI":"10.1137\/1.9781611972757.14"},{"key":"B55","first-page":"64","volume":"28","author":"Yarkony J","year":"2015","journal-title":"Adv. Neural Inform. Processing Systems"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2024.0903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:21:08Z","timestamp":1776068468000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2024.0903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2024.0903"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2024.0903","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}