Optimisation en ligne

Cet article ne cite pas suffisamment ses sources (janvier 2018).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

L'optimisation en ligne est un domaine de l'optimisation mathématique, de plus en plus populaire dans les sciences de l'informatique et dans la recherche opérationnelle, qui traite les problèmes d'optimisation ayant une connaissance incomplète de l'avenir, donc l'optimisation se fait d'une manière en ligne. Ces types de problèmes sont identifiés comme des problèmes en ligne et sont considérés comme opposés aux problèmes d'optimisation classiques où l'information est complète dont l'optimisation se fait d'une manière hors ligne.

L'optimisation en ligne peut se distinguer en deux types. Dans le premier type, le problème est de trouver plusieurs décisions de manière séquentielle, en se basant sur un flux séquentiel de données. Dans le deuxième type, le problème est de trouver une seule décision optimale. Un célèbre exemple du deuxième type est le problème de la location de skis. En général, la sortie d'un algorithme en ligne est comparée à la solution d'un algorithme hors ligne qui est toujours optimale et qui connaît l'ensemble des données en avance.

Dans de nombreuses situations, les décisions du présent (par exemple, l'allocation des ressources) doit être faite avec une connaissance partielle de l'avenir ou avec des hypothèses sur l'avenir qui ne sont pas fiables. Dans de tels cas, l'optimisation en ligne^[1] peut être utilisée, ce qui est différent des autres approches telles que l'optimisation robuste, optimisation stochastique et les processus de décision de Markov.

Problèmes en ligne

Un problème qui illustre le concept des algorithmes en ligne est le problème du voyageur Canadien. Le but de ce problème est de minimiser le coût de l'atteinte d'une cible dans un graphe pondéré où les arêtes ne sont pas fiables et peuvent être supprimés du graphe. Cependant, la suppression d'une arête (échec) n'est révélée qu'au voyageur, lorsqu'il atteint l'arête finale. Le pire des cas est lorsque toutes les arêtes sont supprimées et le problème se réduit au problème de plus court chemin.

Il y a beaucoup de problèmes qui offrent plus d'un algorithme en ligne comme solution :

• Problème de K-serveur
• Séquençage de tâches
• Bandit manchot (mathématiques)
• Problème du secrétaire
• Problème de la location de Ski
• Problème de la sélection du porte-feuille ^[2]

Références

Articles connexes

• Algorithme online

• Portail de l'informatique théorique
• Portail des mathématiques