Mots-clés: Optimisation, algorithme en-ligne, apprentissage en-ligne
Dans ce stage, il s'agit d'étudier des problèmes d'optimisation "multi-étapes" [1, 2, 8] en s'inspirant des méthodes utilisées dans les domaines de l'apprentissage en-ligne [4] d'une part et de l'algorithmique en ligne [5] d'autre part. Dans un problème d'optimisation multi-étapes, on se donne un horizon de temps de T étapes et une séquence d'instances I_1, I_2, ..., I_T et notre objectif est de déterminer une séquence de solutions S_1, S2, ... , S_T conduisant à un compromis entre la qualité de la solution à chaque étape et la stabilité des solutions dans des étapes consécutives. En effet, l'approche consistant à calculer une bonne solution à chaque étape t sans prendre en compte les solutions dans les étapes t-1 et t peut produire une séquence très couteuse en termes de coût de transition entre les différentes solutions. La prise en compte du coût de transition rend certains problèmes beaucoup plus difficiles dans le cas de l'optimisation multi-étapes. C'est le cas du problème du couplage de poids minimum ou du problème de l'arbre couvrant de poids minimum [2, 8]. Pour d'autres problèmes comme les sac-à-dos, on peut déterminer un schéma d'approximation polynomial dans le cas de l'optimisation multi-étapes. Néanmoins il est impossible de déterminer un schéma d'approximation fortement polynomial contrairement au cas statique où un tel schéma existe [3].
On se propose ici de considérer le cas où les instances ne sont pas toutes connues à l'avance. A une étape t, on peut connaitre l'instance I_t, ou l'on peut avoir une fenêtre de prévision limitée. Comme dans le cas hors-ligne, on doit construire une séquence de solutions garantissant un bon compromis entre la qualité et le stabilité. Pour cela, nous comptons essayer d'utiliser les techniques de l'apprentissage en-ligne et de l'algorithmique en ligne. En effet, l'apprentissage en-ligne se concentre sur la notion de 'regret minimization', où l'on mesure la qualité d'une solution par rapport à une solution qui ne change pas (ou de manière limitée) au cours du temps. De l'autre côté, dans le cadre de l'algorithmique en ligne, on se compare à la meilleure solution hors-ligne en permettant autant de changements que nécessaire. Des notions comme le rapport "non-équitable" de compétitivité [4] ou les approches primales-duales développées pour rapprocher ces deux domaines [6, 7] devraient être utiles dans notre étude.
Le travail va donc consister en une étude bibliographique préliminaire, puis en l'étude d'un problème d'optimisation classique dans le cadre multi-étapes. Un problème candidat est le problème du sac-à-dos continu.
La particularité de ce problème est d'être résoluble par un algorithme glouton dans le cadre statique. Sa
résolution hors-ligne dans le cadre multi-étapes nécessite la résolution d'un programme linéaire mais reste
polynomiale, rendant donc l'étude du cas en ligne, ou plus généralement le cas avec fenêtre de prédiction, intéressante
Références
[1] E. Bampis, B. Escoffier, S. Mladenovic, Fair Allocation Over Time, AAMAS 2018.
[2] E. Bampis, B. Escoffier, M. Lampis, V. Paschos, Multistage Matchings, SWAT 2018.
[3] E. Bampis, B. Escoffier, A. Teiller, Multistage Knapscack, soumis 2018.
[4] A. Blum and C. Burch. On-line learning and the metrical task system problem. In COLT, 1997.
[5] A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge University Press,
1998.
[6] N. Buchbinder, S. Chen, J. Naor, O. Shamir, Uni ed Algorithms for Online Learning and Competitive
Analysis, 25th Annual Conference on Learning Theory, vol 23 (2012) 5.15.18.
[7] N. Buchbinder, S. Chen, J. Naor, Competitive Analysis via Regularization, SIAM SODA 2014 436-444.
[8] A. Gupta, K. Talwar, U. Wieder. Changing bases: multistage Optimization for Matroids and Matchings.
ICALP 2014: 563-575.