L’Ecole doctorale EDITE – Ecole doctorale informatique, télécommunications et électronique et Télécom SudParis avec le Laboratoire de recherche SAMOVAR –
présentent
l’AVIS DE SOUTENANCE de Monsieur Guanglei WANG
Autorisé à présenter ses travaux en vue de l’obtention du Doctorat de Télécom SudParis avec l’Université Paris 6 en :
Réseaux, Information et Communications
«Relaxations en programmation mixte en nombres entiers avec contraintes quadratiques et en programmation robuste»
Quand:le 28 novembre 2016 à 14H30
Où:Salle 1C-08, Orange Gardens – 44 Avenue de la République, 92320 Châtillon
Membres du jury :
Directeur de thèse : Walid BEN AMEUR – Professeur
Rapporteurs :
Dritan Nace, Professeur, Heudiasyc-CNRS, Université de Technologies de Compiègne
Leo Liberti, Directeur de recherche, LIX, CNRS, Ecole polytechnique
Examinateurs :
Sourour Elloumi, Professeur, ENSTA ParisTech
Evripidis Bampis, Professeur, LIP6, CNRS, Université Pierre et Marie Curie
José Neto, Maître de Conférences, SAMOVAR, CNRS, Telecom SudParis
Adam Ouorou, Orange Labs Recherche
Résumé :
Le problème d’affectation des machines virtuelles dans le cloud est la motivation initiale de cette thèse qui fait intervenir des contraintes quadratiques en 0-1. Typiquement, un utilisateur peut demander à exécuter une application qui consiste en une demande d’un nombre donné de machines virtuelles avec des demandes de ressources. La première phase du déploiement d’une application est de décider de l’affectation des machines virtuelles constituant l’application à un certain nombre de machines physiques. Généralement, ce placement se fait en optimisant un objectif (maximiser le nombre de machines physiques libres) sous des contraintes exprimant les besoins des utilisateurs et les contraintes des administrateurs du data center.
La structure combinatoire du problème est assez complexe car il contient l’affectation quadratique et les problèmes de sac-à-dos quadratiques. La possibilité de traiter ce problème repose en grande partie sur le développement de techniques mixtes de la programmation entière avec contraintes quadratiques (MIQCP). Cependant, même si des progrès importants ont été réalisés, les résultats « révolutionnaires » sont encore à venir et de nombreux problèmes fondamentaux ne sont pas encore traités. En effet, la relaxation linéaire standard conduit à un grand écart, tandis que les techniques comme la relaxation semi-définie est informatiquement coûteuse dans la procédure de Branch-and-bound. Ainsi, le développement des techniques et des programmes de relaxation efficaces pour le modèle déterministe est la tâche centrale pour le problème d’affectation des machines virtuelles sur les machines physiques.
Pour traiter ce problème nous avons renforcé les relaxations des programmes MIQCP en utilisant les méthodes de type RLT (Techniques de Reformulation et Linéarisation) et en ajoutant de nouvelles inégalités valides. Nous avons également proposé une décomposition Lagrangienne efficace permettant d’avoir des bornes meilleures que celle de la relaxation continue.
Stimulés par ce problème, nous avons étudié le problème de calcul d’enveloppes convexes de fonctions bilinéaires sur l’hypercube. Nous avons obtenus des estimateurs basés sur la SDP (Programmation semi-définie-positive), d’autres en projettant sur des sous-espaces, et une troisième catégorie basée sur un lien qu’on montré entre une certaine fonction polyédrique et les fonctions bilinéaires.
Motivés ensuite par le problème d’affectation avec des exigences incertaines, nous avons développé un nouveau paradigme général pour les programmes linéaires avec paramètres incertains dans le cadre de l’optimisation robuste. Les programmes linéaires avec des paramètres incertains peuvent en effet être très difficiles si l’on considère des approches complètement dynamiques. Ainsi, des politiques plus restrictives doivent être proposées. En outre, dans la pratique, les paramètres incertains d’un problème d’optimisation peuvent être parfois difficiles à observer. Nous proposons le paradigme d’optimisation multipolaire robuste intégrant ces contraintes et répondant aux attentes.