Abstract : This computational paper presents a method to solve k-cluster problems exactly by intersecting semidefinite and polyhedral relaxations. Our algorithm uses a generic branch-and-bound method featuring an improved semidefinite bounding procedure. Extensive numerical experiments show that this algorithm outperforms the best known methods both in time and ability to solve large instances. For the first time, numerical results are reported for k-cluster problems on unstructured graphs with 160 vertices.
https://hal.inria.fr/hal-00717212
Contributeur : Nathan Krislock
<>
Soumis le : vendredi 6 février 2015 - 19:20:54
Dernière modification le : mercredi 11 avril 2018 - 01:59:25
Document(s) archivé(s) le : dimanche 16 avril 2017 - 04:18:26
