TFE 2009-2010 (final year project)

Recherche du vecteur le plus court d'un treillis entier par décomposition

Un treillis entier est l'ensemble des vecteurs obtenus par combinaisons entières d'une base de vecteurs entiers. La recherche du vecteur le plus court d'un treillis est un problème extrêmement difficile qui trouve des applications dans tous types de problèmes où l'objectif est de trouver une solution entière se rapprochant le plus possible d'un modèle continu. C'est par exemple le cas d'une situation où l'on doit trouver une affectation d'objets (ou de tranches horaires) ne favorisant personne dans un groupe. Le cas de deux vecteurs dans la base est l'unique cas pour lequel on peut résoudre le problème efficacement. Le but du mémoire est d'expérimenter l'idée de décomposer le treillis en plusieurs petits treillis sur lesquels on optimise, pour ensuite combiner les sous-optimisations.

Renseignements, Promoteur: