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