Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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].
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-00934727
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 avril 2014 - 15:52:56
Dernière modification le : mardi 19 octobre 2021 - 11:02:56
Archivage à long terme le : : samedi 8 avril 2017 - 21:43:29

Fichier

279.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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⟩

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

366