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.
Paru en mars 2016 , 24 pages