Cette thèse a été réalisée au laboratoire G-SCOP dans l'équipe GROG, et a été
encadrée par :
- Nadia BRAUNER, Directrice de thèse - Professeure des Universités, Université Grenoble Alpes
- Nicolas CATUSSE, Co-encadrant - Maître de Conférences, Grenoble INP - UGA
Les membres du jury :
- François CLAUTIAUX, Rapporteur, Professeur des universités, Université de Bordeaux
- Christoph DURR, Rapporteur, Directeur de recherche, CNRS LIP6
- Eric GAUSSIER, Examinateur, Professeur des universités, Université Grenoble Alpes
- Michaël POSS, Examinateur, Directeur de recherche, CNRS LIRMM
- Bertrand SIMON, Examinateur, Chargé de recherche, CNRS LIG
- Christine SOLNON, Examinatrice, Professeure des universités, INSA Lyon
Résumé (court) :
Les algorithmes online doivent prendre des décisions sans connaître à l’avance toutes les données du problème qui sont dévoilées séquentiellement. Un problème online peut se voir sous forme d’un jeu à deux joueurs entre un algorithme et un adversaire. On peut alors appliquer des méthodes computationnelles classiques de théorie des jeux qui construisent des stratégies afin d’obtenir à la fois des algorithmes et des bornes sur les meilleurs algorithmes possibles.
Après avoir proposé des techniques pour améliorer de telles méthodes computationnelles, on étudie les algorithmes aléatoires et les algorithmes avec prédictions. La pertinence des méthodes est illustrée sur le problème du bin stretching, où des objets doivent être mis dans un nombre déterminé de boîtes afin de minimiser la taille de la plus grande boîte. Pour ce problème, on améliore des bornes connues sur la qualité des algorithmes. On traite également d’aspects théoriques, comme la convergence, des méthodes computationnelles.
Résumé (long) :
Dans un problème d'optimisation online, l'ensemble des données d'un problème à résoudre n'est pas connu à l'avance mais est révélé par parties au fil du temps. Un décideur, ou algorithme, doit prendre des décisions avec une connaissance partielle du problème, et une décision prise tôt peu se révéler être mauvaise bien plus tard. Ces problèmes sont souvent étudiés selon l'analyse compétitive, qui mesure le pire cas par rapport à une solution optimale avec information complète, dite offline. Pour trouver ce pire cas, on peut classiquement considérer le problème comme un jeu à deux joueurs entre un algorithme qui prend des décisions et un adversaire qui va révéler le problème petit à petit. On cherche alors à calculer des bornes théoriques sur les performances possibles d'algorithmes online. De telles bornes sont souvent des études de cas de longueur conséquente qui proposent un pire cas pour chaque algorithme possible. L'objet de cette thèse est de proposer des méthodes par ordinateur pour construire de telles études de cas pour des algorithmes online dans différents paradigmes.
De telles méthodes sont appliquées sur le problème du online bin stretching. Pour ce problème, on dispose de m boîtes, unidimensionnelles et de taille unitaire. Une séquence d’objets définis par leur taille est reçue de manière online: on reçoit les objets l'un après l'autre, et un objet doit être placé dans une boîte de manière irrévocable avant de recevoir le suivant. Cette séquence d'objets est garantie de rentrer dans les m boîtes de taille unitaire. Il est possible de placer un objet dans une boîte sans tenir compte de la capacité de la boîte (d’où le terme stretching). L’objectif est de minimiser le volume de la boîte la plus remplie. Si les objets sont tous connus à l’avance, un algorithme offline peut les faire rentrer dans m boîtes de taille 1. Cependant, lorsque les objets sont donnés de manière online, il peut être nécessaire d’utiliser des boîtes de taille supérieure. Pour ce problème, plusieurs des meilleures bornes inférieures connues sur la meilleure performance possible d’un algorithme ont été obtenues de manière computationnelle. De même, plusieurs des meilleurs algorithmes connus proviennent de recherches computationnelles.
Cette thèse propose dans un premier temps des améliorations techniques des méthodes computationnelles pour trouver des bornes sur le bin stretching, ce qui permet l'obtention de meilleures bornes. Une fondation théorique à ces méthodes est donnée en démontrant leur convergence sur le problème du bin stretching. L'analyse classique au sens du pire cas n'est pas nécessairement pertinente dans des cas pratiques; d'autre paradigmes d'études existent pour contourner ce problème, notamment ceux des algorithmes aléatoires et des algorithmes avec prédictions. Ces paradigmes complexifient cependant la notion de ce qu'est un algorithme ce qui rend leur construction et analyse difficile.
Les algorithmes aléatoires prennent des décisions de manière stochastique, ce qui empêche l'adversaire qui cherche à proposer le pire cas de réagir parfaitement à chaque coup de l'algorithme. On propose ici notamment une méthode à base de programmation linéaire pour obtenir des bornes sur l'espérance de la performance d'algorithmes aléatoires; un algorithmes aléatoire meilleur que les meilleurs algorithmes connus est aussi construit pour le bin stretching. Dans le paradigme d'algorithmes avec prédictions, les algorithmes ont accès à une prédiction plus ou moins précise et dont la qualité n'est pas connue. L'objectif est alors de proposer des algorithmes qui sont très performants lorque cette prédiction est précise sans trop y perdre lorsqu'elle est imprécise. L'objectif n'est donc plus unidimensionnel comme précédemment: il y a un équilibre à trouver entre faire confiance à la prédiction donnée et en douter. On propose alors une méthode pour construire des bornes inférieures sur les fonctions de performance d'algorithmes avec prédictions.
