|
|
Mardi 8 Janvier
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Aller-retour et voyageur de commerce dans les réseaux de transports urbain |
Description: |
Pierre Parent Le problème de l'aller-retour se pose lorsque l'on dispose d'un véhicule personnel, et que l'on peut faire une partie du trajet à l'aide de celui-ci, et le restant via les transports en communs. Il s'agit alors de trouver quel trajet choisir à l'aller et au retour, pour minimiser le temps total, sachant que si la voiture est garée à un endroit à l'aller on doit passer la rechercher à ce même endroit au retour.
Dans le problèmes de voyageur de commerce nous avons un certain nombre d'endroit à visiter en ville, et il s'agit de trouver le trajet optimal passant par tout ces points en utilisant les transports en commun. La difficulté réside dans le fait que les trains, arrivent et partent à des heures fixées de la journée.
Nous proposerons des méthodes de résolution pour les deux problèmes, ainsi que des résultats expérimentaux. |
Mardi 29 Janvier
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Combinaison automatique d'algorithmes et heuristiques |
Description: |
Yanik Ngoko Sur de nombreux problèmes combinatoires comme SAT ou CSP, on peut facilement trouver, étant donné un sous ensemble d'heuristiques, un sous ensemble d'instances du problème sur lequel aucune heuristique ne domine complètement les autres(*). Ceci a motivé de nombreux travaux ayant pour but de combiner plusieurs heuristiques résolvant le même problème afin d'exploiter leur diversité.
Dans cet exposé, nous nous intéressons à cette problématique en contexte parallèle et homogène. Dans les solutions décrites, une combinaison est obtenue en exécutant de façon concurrente dans le temps et dans l'espace (coeurs, processeurs, régistres caches etc.) plusieurs heuristiques, jusqu'à ce que l'une d'elles trouve une solution satisfaisante. Pour apprendre à construire de telles combinaisons, nous proposons une solution d'apprentissage basée sur une estimation du temps d'exécution des heuristiques sur un jeu d'instances représentatives. Le coeur de notre proposition peut être formulé comme un  problème combinatoire dont nous prouvons la  np-completude et l'inapproximabilité. Nous proposons pour sa résolution plusieurs heuristiques, avec garanti de performance sous certaines hypothèses.
Finalement, nous présentons quelques résultats de notre approche de combinaison sur les problèmes SAT et CSP.
(*) Par exemple dans le temps pris pour donner une solution satisfaisante.. |
|
|