Skip to Main content Skip to Navigation
Conference papers

Coloriage de graphe en programmation par contraintes

Nicolas Barnier 1 Pascal Brisset 2
1 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Résumé : 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].
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-00934727
Contributor : Laurence Porte <>
Submitted on : Thursday, April 17, 2014 - 3:52:56 PM
Last modification on : Wednesday, July 24, 2019 - 11:48:02 PM
Document(s) archivé(s) le : Saturday, April 8, 2017 - 9:43:29 PM

File

279.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00934727, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

382

Files downloads

420