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)

1 Department of Mathematical Sciences
2 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
3 LIPN - Laboratoire d'Informatique de Paris-Nord

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.

Mots clés: k-densest subgraph problem; k-cluster problem; triangle inequalities; combinatorial optimization; semidefinite programming

Domaines: Optimisation et contrôle [math.OC]; Mathématique discrète [cs.DM]; Recherche opérationnelle [math.OC]

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, 2016, 66, pp.153-159. ⟨10.1016/j.cor.2015.07.008⟩. ⟨hal-00717212v6⟩