Retour

G-2016-17

Computational study of valid inequalities for the maximum k-cut problem

, et

référence BibTeX

Nous considérons le problème de la k-coupe maximale qui consiste à partitionner l'ensemble des sommets d'un graphe en k sous-ensembles tels que la somme des poids des arêtes entre les différents sous-ensembles soit maximale. Nous nous concentrons sur l'identification de classes efficaces d'inégalités pour améliorer la valeur de la relaxation semi-définie du problème. Nous réalisons l'étude expérimentale de quatre classes d'inégalités : clique, genclique, wheel, et biwheel. Nous avons considéré 10 combinaisons de ces classes que nous avons testées sur des instances denses et creuses pour k{3,4,5,7}. Les résultats suggèrent que biwheel et wheel sont les inégalités les plus fortes pour k=3, et que pour k{4,5,7}, les inégalités de type wheel sont de loin les plus fortes. Par ailleurs, on note une amélioration de la performance pour tout k lorsque les inégalités de type biwheel et wheel sont utilisées conjointement, au coût de 72% de plus de temps CPU, en moyenne, par rapport à l'utilisation d'un seul de ces types.

, 24 pages

Publication

, et
Annals of Operations Research, 265(1), 5–27, 2018 référence BibTeX