Mixed-integer programming techniques for the minimum sum-of-squares clustering problem

Jan Pablo Burgard (), Carina Moreira Costa (), Christopher Hojny (), Thomas Kleinert () and Martin Schmidt ()
Additional contact information
Jan Pablo Burgard: Trier University
Carina Moreira Costa: Trier University
Christopher Hojny: Eindhoven University of Technology
Thomas Kleinert: Quantagonia GmbH
Martin Schmidt: Trier University

Journal of Global Optimization, 2023, vol. 87, issue 1, No 5, 133-189

Abstract: Abstract The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop and test different tailored mixed-integer programming techniques to improve the performance of state-of-the-art MINLP solvers when applied to the problem—among them are cutting planes, propagation techniques, branching rules, or primal heuristics. Our extensive numerical study shows that our techniques significantly improve the performance of the open-source MINLP solver SCIP. Consequently, using our novel techniques, we can solve many instances that are not solvable with SCIP without our techniques and we obtain much smaller gaps for those instances that can still not be solved to global optimality.

Keywords: Minimum sum-of-squares clustering; Mixed-integer nonlinear optimization; Global optimization; Computational techniques; 90C10; 90C11; 90C57; 90-08 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01267-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:87:y:2023:i:1:d:10.1007_s10898-022-01267-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01267-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().