Colloque

Recherche à voisinage variable de graphes extrêmaux

G. Caporossi

P. Hansen

Membre a labase

G. Caporossi

Résumé du colloque

On considère le problème de déterminer des graphes extrêmaux pour des expressions dépendant d'un ou plusieurs invariants comme un problème d'optimisation globale. La recherche par voisinage variable, une métaheuristique récente, est utilisée pour le résoudre. Les voisinages sont définis par l'addition, la suppression et l'échange d'arêtes, la suppression de sommets pendants et ainsi de suite. On présente les premiers résultats obtenus avec le programme AutoGraphiX : on réfute trois conjectures de Graffiti, on en renforce plusieurs autres et on en présente de nouvelles.