Résolution de problèmes de domination de graphe par la programmation mathématique

On appelle un ensemble dominant dans un graphe un ensemble D de noeuds du graphe tel que tout noeud v du graphe est dans D ou relié à un noeud de D par une arête. Le problème de déterminer un ensemble dominant de cardinalité minimum est un problème classique en théorie des graphes, et possède de nombreuses variations.

L'objectif du mémoire serait d'effectuer une revue de la littérature sur ce problème et quelques-unes de ces variantes, et de proposer et tester de nouvelles formulations de programmation en nombres entiers pour résoudre ces variantes.

Contact:

Résolution du problème de «packing coloring»

Le problème de coloration de graphe consiste à trouver le nombre minimum de couleurs (appelé nombre chromatique) nécessaire pour colorier les noeuds du graphe de telle sorte que deux noeuds voisins aient des couleurs différentes.

Récemment, une variante de ce problème, le /packing coloring/ a été proposée. Une /k-packing-coloratin/ d'un graphe est une coloration du graphe avec /k/ couleurs telle que deux noeuds de couleurs /i/ soient distants d'au moins /i+1/. Le problème étudié consiste à trouver le plus petit /k/ pour lequel une telle coloration existe.

Jusqu'à présent, des résultats théoriques pour des graphes particuliers ont été proposés, mais aucune méthode n'a été proposée pour résoudre le problème général. Le but du mémoire est de proposer et tester des formulations de programmation en nombres entiers pour ce problème.

Contact:

Développement d'une librairie de modélisation mathématique en clojure

Le langage Clojure est un langage fonctionnel, basé sur la JVM, qui est de plus en plus utilisé (par exemples pour les applications webs). Le but du travail est de développer une librairie permettant de modéliser des problèmes linéaires et en nombres entiers de manière générique en clojure et de fournir une interface vers différents solveurs (glpk, cplex, gurobi, ...)

Contact:


Pour d'autres propositions, contactez ou Martine Labbé.