Sujets de TER pour les masterM1


Année 13-14


TITRE : Le problème du voyageur de commerce alterné
Descriptif et objectifs :



Ce problème est une variante du fameux problème du voyageur de commerce. Dans ce problème nous disposons de n partitions et nous cherchons un chemin Hamiltonien de coût minimum tel que deux sommets consécutifs appartiennent à deux partition différentes. De plus,  l'ordre de visite des partitions est toujours la même. A contrario, du voyageur classique, ce problème est approximation. Le but de ce stage est de comparer les divers heuristiques avec garantie de perfromance en partique, et de proposer d'autres algorithmes de votre cru.


Encadrant
: Giroudeau rodolphe
Mail : rgirou@lirmm.fr




TITRE : 
Le problème de la génération de colonnes
Descriptif et objectifs :

Cette technique est utilisée pour résoudre des problèmes linéaires ayant un très grand nombre de variables, ce qui ne permet pas d'appliquer l'algorithme du simplexe sur ces problèmes dans leur globalité.Le but de ce stage est  comprendre et d'appliquer le principae de génération de colonnes à des exemples classiques de de l'optimsiation combinatoire. Il est également prévu de comparer les génération de colonnes  aux algorithmes Primal-Dual.

Encadrant
: Giroudeau rodolphe
Mail : rgirou@lirmm.fr


TITRE : Le problème du Bin-Packing et ses variantes
Descriptif et objectifs : Le problème de Bin-packing consiste à mettre dans des boites de tailles identiques des objets de différentes tailles, et le but est de   minimiser le nombre de boîtes. Le but de ce stage est de synthétiser les résultats existants, de comparer sur des jeux d'instances les différents algorithmes. De plus, vous étudierez également  les algorithmes  où des objets sont  incompatibles avec certaines boîtes.
Encadrant : Giroudeau rodolphe et Jean-Claude König
Mail :  rgirou@lirmm.fr, konig@lirmm.fr




TITRE : Sur l'étude des algorithmes d'approximation de schéma polynomial (PTAS) et totalement polynomial (FPTAS)
Descriptif et objectifs :

Les algorithmes d'approximation de schéma polynomial et totalement polynomial sont des algorithmes d'appproximation de rapport aussi proche que l'on veut de la solution optimale. Le ratio de la performance relative est de 1+epsilon. Il est évident que ce ratio proche de un  induit un surcoût sur la complexité de l'algorithme. Dans ce TER, nous étudierons les principes qui régissent ces algorithmes, et nous illustrerons par des exemples sur des problèmes classiques en optimisation combinatoire. Vous validerez vos observations par des tests.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr


TITRE : Développement d'une application Web sur des problèmes d'ordonnancement
Descriptif et objectifs :

Ce stage porte le développement d'une applciation Web pour visualiser des diagrammes de Gantt . Les problèmes d'ordonnancement consistent à affecter des tâches  à des processeurs. Dans ce stage,  nous proposerons plusieurs algorithmes concernant  divers modèles.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr

TITRE : A forward-backward algorithm for single-source shortest path
Descriptif et objectifs :

Très récemment David Wilson et Uri Zwick ont proposé un nouvel algorithme pour le problème du plus court chmein à partir d'une source. Le but de ce stage est de comprendre l'article et de comparer leur résultats avec des algorithmes classiques.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
Last modified: Fri Dec 17 15:17:12 CET 2004