Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Doctoral studies

Thesis of

Trong-Tuan Vu

Friday 12 December 2014
Amphithéâtre de l'IRCICA

Robust peer-to-peer algorithms for large scale combinatorial optimisation problems

Directeur de Thèse : Prof. Nouredine MELAB Rapporteurs : Prof. Pierre SENS et Prof. Daniel TUYTTENS Membres : - Rapporteurs * Pierre Sens, Professeur à l'Université de Paris 6 * Daniel Tuyttens, Professeur à l'Université de Mons, Belgique - Examinateurs * Akka Zemmari, Maître de Conférences à l'Université de Bordeaux * Jean-Stéphane Varré, Professeur à l'Université Lille 1 - Directeurs * Nouredine Melab, Professeur à l'Université Lille 1 * Bilel Derbel, Maître de Conférences à l'Université Lille 1

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle.

Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entiré de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocols spécifiques à des contextes homogènes, hétérogène en terme de pussance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster