Travaux de recherche sur la coloration de graphe réalisés en 2ème année d'école d'ingénieur.
Travaux expérimentaux, basés sur des techniques de programmation linéaire en nombres entiers et de programmation par contrainte.
Le dossier final contient l'intégralité du travail finalisé.
Identifier préalablement la clique max (par exemple en utilisant cliquer) et spécifier ses sommets en premiers dans le modèle réduira considérablement le temps de calcul.
On peut utiliser ces modèles pour colorier des graphes aléatoires jusqu'à 1000 sommets ou des graphes difficiles (tels que les Mycielski) jusqu'à 70 sommets.
Voir la compte rendu (final/documents/compte_rendu.pdf) pour plus de détails.