Skip to Main content Skip to Navigation
Journal articles

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
* Corresponding author
2 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology, LJK - Laboratoire Jean Kuntzmann
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.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00717212
Contributor : Nathan Krislock <>
Submitted on : Friday, February 6, 2015 - 7:20:54 PM
Last modification on : Tuesday, May 11, 2021 - 11:37:32 AM
Long-term archiving on: : Sunday, April 16, 2017 - 4:18:26 AM

File

manuscript_COR3.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

1023

Files downloads

1707