Newsletter #4

Optimisation combinatoire : Problème de la Somme Coloration Minimale Par Clément Lecat

Les problèmes d'optimisation combinatoire permettent de modéliser un ensemble de problèmes de la vie courante et de déterminer une solution optimale ou de qualité pour y répondre. Nos travaux se sont portés sur l'un de ces problèmes : le problème de la Somme Coloration Minimale (MSCP) d'un graphe G. L'objectif de MSCP est de déterminer une solution valide minimisant la somme des poids associés aux couleurs utilisées. Cette somme est appelée la somme chromatique, notée ∑(G)Le nombre minimal de couleurs nécessaire à l'obtention d'une solutin minimale pour MSCP est appelée la force du graphe, notée s(G). Celle-ci peut être arbitrairement plus grande que le nombre chromatique du graphe, noté χ(G), qui est le nombre minimal de couleurs nécessaire à l'obtention d'une coloration valide d'un graphe. MSCP trouve ses applications dans de nombreux domaines, tels que l'allocation de ressources distribuées, les problèmes d'ordonnancement, et plus particulièrement la gestion des flux (population, réseaux, transports...) pour laquelle MSCP a la particularité d'apporter une solution permettant de garantir la qualité de service, en minimisant le délai moyen d'attente...

 

   

Thème: