De Ensiwiki.

Quelle taille de graphe peut-on colorier optimalement avec un ordinateur aujourd'hui ?

Thème général

Le but de ce projet est de répondre à cette question, que se posent régulièrement les industriels. En effet, le problème de la coloration de graphes apparaît fréquemment dans des situations de production où une ressource est partagée par plusieurs éléments ayant des incompatibilités entre eux. Par exemple, on peut faire passer plusieurs pièces simultanément dans un four industriel, à condition qu'il y ait une température de cuisson possible qui soit commune à toutes les pièces du lot. Pour des raisons d'économie des coûts, l'industriel cherche à partager l'ensemble des pièces en un nombre minimum de lots compatibles.

Ce problème se modélise comme un problème de coloration d'un graphe non orienté. A chaque pièce correspond un sommet; deux pièces sont jointes par une arête si leurs températures de cuisson sont incompatibles. On cherche alors une affectation de couleurs aux sommets du graphe, de sorte que deux sommets voisins reçoivent des couleurs différentes. Dans l'exemple précédent, un lot correspond à une couleur. On désire une coloration avec un nombre minimum de couleurs: ce nombre est appelé nombre chromatique du graphe. Les deux problèmes qui nous préoccupent sont donc le calcul du nombre chromatique d'un graphe, et le calcul d'une coloration valide du graphe employant le nombre mininum de couleurs.

Les approches algorithmiques, et les développements théoriques autour de la coloration de graphe, sont nombreux. Il est demandé ici de se limiter aux algorithmes fournissant une coloration d'un graphe avec le nombre de couleurs optimal. Le problème étant NP-complet, il n'y a pas d'espoir de trouver un algorithme efficace pour le résoudre.

Néanmoins, de nombreuses approches existent pour résoudre ce problème de manière exacte (mais en temps non polynomial). L'objectif de ce projet est de déterminer la ou lesquelles de ces méthodes sont les plus efficaces pour le problème de la coloration, et d'estimer quelle taille de graphes peuvent être traîtés avec ces méthodes.

Ainsi, si ce travail conclut que "on peut colorier aujourd'hui, en moins d'un jour de temps calcul, un graphe de 60 sommets", un industriel confronté à la coloration d'un graphe de 100 sommets saura qu'il devra se résoudre à employer des méthodes approchées, c'est-à-dire employant un nombre de couleurs peut-être plus grand que le minimum possible.

Tâches envisagées:

- Travail de bibliographie

- Formulations du problème en programmation linéaire en nombres entiers (PLNE)

- Recherche d'instances classiquement utilisées dans le monde académique pour quantifier la vitesse et la qualité des algorithmes de coloration

- Prise en main de logiciels de résolution de PLNE

- Résolution de ces instances par la PLNE

- Recherche des heuristiques les plus couramment utilisées pour la coloration

- Résolution à l'aide de ces heuristiques

- Analyse et interprétation des données numériques

L'approche proposée ci-dessus peut être enrichie suivant la créativité du groupe candidat. En particulier, d'autres approches algorithmiques peuvent être envisagées: méta-heuristiques, algorithmes de populations, nouveaux algorithmes ad-hoc faits maison...