Optimisation dans l'Incertain (OI)
- Titre :
- Optimisation dans l'Incertain (OI)
- Section :
- Obligatoire
- État pour cette année :
- OPEN
- Mots clés :
- Programmation Stochastique, Programmation Dynamique
- Ects :
- 3
- Responsable :
- Vincent Leclère (ENPC ParisTech / CERMICS)
- Intervenants :
-
Vincent Leclère (ENPC ParisTech / CERMICS)
- Prérequis :
bases de probabilité, programmation et dualité linéaire, décomposition de Benders
- Objectif :
Objectif à préciser
- Contenu / Plan :
Séance 1 Introduction à l’optimisation sous incertitude.
- Grandes classes de problème d’optimisation sous incertitude parmis lesquels l’optimisation stochas- tique 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
Compétences visées
- 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 ;
- Bibliographie :
-
-
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
-
- Liens :
- (aucun)
- Compétences visées :
-
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.
-
- Modalités de contrôle :
TP à faire hors séance + Examen final