Computational results of a semidefinite branch-and-bound algorithm for k-cluster

Nathan Krislock 1, * Jérôme Malick 2 Frédéric Roupin 3
* Auteur correspondant
2 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2016, 66, pp.153-159. 〈10.1016/j.cor.2015.07.008〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00717212
Contributeur : Nathan Krislock <>
Soumis le : vendredi 6 février 2015 - 19:20:54
Dernière modification le : jeudi 11 janvier 2018 - 06:21:53
Document(s) archivé(s) le : dimanche 16 avril 2017 - 04:18:26

Fichier

manuscript_COR3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathan Krislock, Jérôme Malick, Frédéric Roupin. Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Computers and Operations Research, Elsevier, 2016, 66, pp.153-159. 〈10.1016/j.cor.2015.07.008〉. 〈hal-00717212v6〉

Partager

Métriques

Consultations de la notice

435

Téléchargements de fichiers

162