Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/307510 
Year of Publication: 
2023
Citation: 
[Journal:] Journal of Global Optimization [ISSN:] 1573-2916 [Volume:] 87 [Issue:] 1 [Publisher:] Springer US [Place:] New York, NY [Year:] 2023 [Pages:] 133-189
Publisher: 
Springer US, New York, NY
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.
Subjects: 
Minimum sum-of-squares clustering
Mixed-integer nonlinear optimization
Global optimization
Computational techniques
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.