Groupe d’études et de recherche en analyse des décisions

G-2016-17

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

, et

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 \in \{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 \in \{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