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: Bernard Fortz

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: Bernard Fortz

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: Bernard Fortz

Optimisation de patrouilles d'inspection sur une ligne de transport public

Le but du mémoire est l'étude de la litérature concernant les stratégies à adopter pour établir les horaires d'équipes de contrôle sur une ligne de transport en commun, et d'implémenter et comparer plusieurs modèles d'optimisation pour résoudre ces problèmes.

Contact: Bernard Fortz bernard.fortz@ulb.ac.be

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

Parmi les langagest fonctionnels, Haskell est un langage fortement typé qui permet aisément le développement de languages dédiés à un domaine. 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 haskell et de fournir une interface vers différents solveurs (glpk, cplex, gurobi, ...)

Contact: Bernard Fortz


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