PGMO Seminars 2012
18 Décembre 2012 : Méthodes d'optimisation stochastique en finance et applications
- Nadia Oudjane (EDF R&D) "Méthodes de particules en interaction pour les problèmes d'arrêt optimal et applications à la valorisation de centrales électriques"
- Olivier klopfenstein (EDF R&D) et Laurent Pfeiffer (Ecole Polytechnique) "Contrôle Stochastique Optimal pour la gestion Actif-Passif"
20 Novembre 2012 : Optimisation des vallées hydroélectriques
- Anes Dallagi et Tomas Simovic (EDF R&D) "Optimisation des actifs hydrauliques d'EDF : besoins métiers, méthodes actuelles et perspectives"
L'une des difficultés majeures dans la gestion de production électrique est que cette énergie n'est pas (ou difficilement) stockable. C'est pourquoi la gestion des actifs hydro-électrique revêt une importance capitale pour EDF. Ces actifs permettent de transférer ou de différer dans le temps les productions d'énergie vers les plages temporelles les plus intéressantes. Cette présentation s'attachera dans une première partie à la description des processus d'optimisation et les méthodologies actuellement utilisées. La deuxième partie sera consacrée à la présentation des travaux de recherches en court et en préparation pour répondre à certaines problèmatiques métier
- Claudia D'Ambrosio (LIX-Ecole Polytechnique) "Optimality for tough combinatorial hydro-valleys problems"
In this talk we present the research directions we are planning to explore within the context of the PGMO project "Optimality for tough combinatorial hydro-valleys problems" and of a PhD in collaboration with EDF R&D. The aim of the project is to study a crucial problem in energy management: the Unit Commitment sub-problem dedicated to hydro valley management. When continuous, such a problem is easily solved to optimality by any current LP solver. However, the introduction of combinatorial elements leads to far tougher hydro valley problems. This is especially true for some of the larger French Hydro valleys (ref. talk of Anes Dallagi and Tomas Simovic). We plan to explore several research directions, from the more classical, i.e., improving and designing heuristic algorithms and using decomposition schemes, to the more ambitious, i.e., employing efficient methods to cast the head effect to the power production function in order to model in a more realistic way the system at hand (with references to linear approximations of two-variables functions).
18 Octobre 2012 : Partitionnement de Graphes
- R. Sirdey (CEA LIST) "Partitionnement stochastique de réseaux de processus"
Dans cet exposé nous parlerons d’un problème de partitionnement de graphe sous contraintes de sac à dos sur les partitions, problème qui se
présente lorsqu’il s’agit de placer un réseau de processus flot de données sur les éléments matériels d’une architecture de processeur massivement multi-cœur. Dans ce contexte, les poids des sommets sont entachés d’une incertitude complexe et difficile à modéliser. Nous présentons donc une approche non paramétrique de prise en compte de cette incertitude et, étant donné la taille des instances à traiter de manière routinière, montrons comment l’intégrer avec peu de déstructuration dans des algorithmes heuristiques préexistant pour le cas déterministe.
- V.H. Nguyen (LIP6) "Solutions exactes pour un problème de partitionnement de graphes avec contraintes de capacité"
Dans cet exposé, nous allons aborder une variante du problème de Partitionnement de Graphes où les sous-ensembles dans la partition ne sont
pas (uniquement) soumis à des contraintes de cardinalité mais (aussi) à des contraintes de capacité. Etant donnés une constante B et un graphe
G=(V,E) où les arêtes sont pondérées. La capacité d'un sous-ensemble S de V est définie comme la somme des poids des arêtes ayant au moins une extrémité dans S. Le problème de Partitionnement de Graphes avec Contraintes de Capacité (PGCC) est de trouver une partition de V dont les
sous-ensembles ont tous une capacité inférieure ou égale à B, qui minimise le poids les arêtes dans l'interconnexion.
On peut trouver cette définition de capacité des sous-ensembles dans les applications diverses. Par exemple, dans le problème de conception des
réseaux optiques de télécommunications SONET/SDH où le poids des arêtes représente le volume de trafic entre deux nœuds d'extrémité, on doit
trouver une partition optimale des nœuds en anneaux respectant la contrainte de capacité.
La capacité d'un anneau représente dans ce cas le volume de trafic total transitant par l'anneau.
Nous rappelons d'abord quelques résultats de complexité montrant PGCC NP-difficile et établissons un nouveau résultat d'inapproximabilité de PGCC.
Nous abordons ensuite la résolution exacte de PGCC. Nous présentons deux formulations entières mixtes appelées respectivement Node-Cluster and Node-Node pour PGCC. Les contraintes de capacité y sont quadratiques non-convexes. Nous discutons des méthodes de convexification/linéairisation de ces contraintes et leur utilisation dans un algorithme de Branch-and-Bound pour PGCC. Les résultats numériques comparant ces méthodes seront présentés.