Optimisation dans l'Incertain (OI)

Vincent Leclère (ENPC ParisTech / CERMICS)

Vincent Leclère (ENPC ParisTech / CERMICS)

3

Programmation Stochastique, Programmation Dynamique

Bases de probabilité, programmation et dualité linéaire, décomposition de Benders

Séance 1 Introduction à l’optimisation sous incertitude.

• Grandes classes de problème d’optimisation sous incertitude parmis lesquels l’optimisation stochastique et robuste. Importance de la simulation dans l’évaluation des problèmes d’optimisation sous incertitude.
• Principe de l’optimisation stochastique. Formulation extensive sur un arbre de scénarios. Notion de structure d’information, VSS et EVPI.
• Principe de Sample Average Approximation.

Séance 2 Méthodes numériques de décomposition des problèmes stochastiques

• Décomposition L-Shaped.
• Progressive-Hedging.
• Extension au cas multistage.

Séance 3 Méthodes de résolution à base de programmation dynamique.

• Principe de la programmation dynamique. Opérateur de Bellman. Application à un problème de gestion de stock.
• Extension du cadre d’application de la programmation dynamique à l’aide d’état étendu : exemples et exercices.
• Algorithme SDDP pour le cas linéaire convexe.

Séance 4 Introduction à l’optimisation robuste.

• Principe de l’optimisation robuste. Motivation par le cas linéaire.
• Classes de méthodes de résolution : génération de contraintes ou reformulation. Exemple du cas linéaire.
• Classification des problèmes robustes. Notion de garantie probabiliste.

Séance 5 Optimisation robuste avancée.

• Problèmesd’optimisationrobustesouscontraintesdebudget.ModèledeSoyster.Modèleaveccontraintes de budget (Bertsimas-Sim). Méthode de reformulation et garanties théoriques.
• Problèmes d’optimisation robuste avec recours. Règles de décision affines. Recours K-adaptable.

Séance 6 Examen

• Lectures on Stochastic Programming, Dentcheva, Ruszczynski, Shapiro

• Dynamic Programming and Optimal Control, Bertsekas

• Theory and applications of robust optimization, Bertsimas, Brown, Caramis

• The Price of Robustness, Bertsimas Sim

• Distributionally robust optimization : A review, Rahimian, Mehrotra

• A survey of adjustable robust optimization Yanıkoğlu, Gorissen, den Hertog

• Savoir modéliser un problème d'optimisation sous incertitude;

• Savoir mettre en place des méthodes de résolution d'un problème stochastique à deux étapes;

• Savoir mettre en place des méthodes de résolution d'un problème d'optimisation robuste linéaire ;

• Savoir utiliser un algorithme de programmation dynamique dans un cadre Markovien simple.

TP à faire hors séance + Examen final