Coloriage de graphe en programmation par contraintes

Nicolas Barnier (1) , Pascal Brisset (2)

1 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
2 ENAC - Ecole Nationale de l'Aviation Civile

Le coloriage optimal d'un graphe (GC) est un problème NP-difficile très classique et un sujet de recherche toujours actif [6], avec de nombreux domaines d'application : scheduling, allocation de ressources, reconnaissance de formes... Comme c'est un problème (NP-)difficile, les techniques approchées figurent en bonne place parmi les algorithmes les plus performants sur les graphes " aléatoires " peu structurés et de grande taille (algorithme glouton [4], recherche locale [5]). Cependant, les algorithmes énumératifs complets de Branch & Bound (B&B) peuvent également être efficaces [2] pour des problèmes plus structurés, par exemple issus d'applications " réelles ", ou de taille moindre. Les deux méthodes principales utilisées pour le GC soit déterminent des classes de couleurs en partitionnant le graphe en stables (independent sets), soit colorie les noeuds séquentiellement (SC, Sequential Coloring). Pour implémenter des algorithmes de SC exact, la Programmation Par Contraintes (PPC) est un outil efficace et élégant [7] : d'une part le problème se modélise naturellement en associant des variables à domaine fini à chaque noeud et des contraintes de diséquation à chaque arête, et d'autre part le B&B est l'algorithme de recherche standard dans les systèmes de PPC. Nous combinons cette modélisation basique avec diverses techniques visant à réduire la taille de l'espace de recherche et guider son exploration. Nous proposons également d'exploiter plus avant la structure des graphes en recherchant un ensemble de cliques avec un algorithme glouton pour améliorer l'inférence et l'ordre d'instanciation des variables [1]. L'algorithme ainsi obtenu permet de résoudre un problème de conception d'un réseau de routes aériennes directes et présente de bonnes performances sur les instances applicatives du banc de tests proposé dans [6].

Mots clés: programmation par contraintes; clique; coloriage de graphe

Domaines: Optimisation et contrôle [math.OC]

Nicolas Barnier, Pascal Brisset. Coloriage de graphe en programmation par contraintes. ROADEF 2003, 5ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2003, Avignon, France. ⟨hal-00934727⟩