Retour aux activités
Séminaire du GERAD

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


24 fév. 2022   10h00 — 11h00

Martin Schmidt Trier University, Allemagne

Martin Schmidt

Présentation sur YouTube

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. We now solve many instances that are not solvable without our techniques and we obtain much smaller gaps for those instances that can still not be solved to global optimality.

Daniel Aloise responsable


Montréal Québec Canada

Axe de recherche

Applications de recherche