Please find below a full-time post-doc position offer on decomposition algorithms for solving generation expansion planning problems.
The post-doc will be co-supervised by Inria Edge & Inocs teams (Bordeaux, France) and EDF R&D (Palaiseau, France).
Starting date: From 2023/10 to 2024/02
Duration: 24 months
Supervision:
- Inria: Ayse Arslan, Boris Detienne and Aurélien Froger (Edge), Bernard Fortz (Inocs), Frédéric Semet (Inocs)
- EDF: Cécile Rottner and Rodolphe Griset (R&D/OSIRIS)
Contact: ayse-nur.arslan@inria.fr<mailto:ayse-nur.arslan@inria.fr>, boris.detienne@inria.fr<mailto:boris.detienne@inria.fr>, aurelien.froger@inria.fr<mailto:aurelien.froger@inria.fr>
Scientific context: Multiple problems studied by the "long-term planning" team in the OSIRIS department
of EDF R&D correspond to making investment decisions over a multi-year planning horizon while taking
into account economic, physical or legal restrictions and grid balancing.
By their nature, these problems can be modeled as multi-stage stochastic optimization problems in the
sense that it is possible to adapt the investment decisions to the realization of uncertainty over the course
of the planning horizon. The requirement to balance the electricity grid results in Unit Commitment (UC)
problems appearing as subproblems. The presence of numerous discrete decisions is a notable characteristic
of these problems.
The complexity and the scale of these problems lead EDF to resort to simplifying assumptions in their
solution (for instance, multi-stage problems are approximated by two-stage ones or mixed-integer linear
problems are approximated by linear problems). Currently, a tool named TiLT ("Long-Term Investment
Trajectories") is used to optimize investment decisions with a multi-year vision where "trajectories" are
used to formulate very large-scale linear models (with millions of variables and constraints). A heuristic
"Investment Loop" is used to fix the investment decisions based on a "Unit Commitment" (UC) solver
called Continental. The team has started working on the solution of the two-stage (meaning that all investment
decisions are taken before the realization of uncertainty) approximation of these problems exploiting
the fact that when investment decisions are fixed the constraints ensuring the electricity grid balance can
be decomposed into independent subproblems by trajectory. Geographical and temporal decoupling is
also used to reduce the size of sub-problems. Decomposition methods - notably Benders or Lagrangian
decomposition - can be used to exploit this type of structure. In a Benders decomposition approach, the
master problem consists of fixing the investment decisions (related to the electricity generation plants)
and subproblems reduce to UC problems.
Solving the targeted investment problems with finer approximations is an important problematic for
obtaining more judicious investment decisions. Taking into account the discrete nature of certain decisions
(for instance switch-on costs of plants, ramping constraints, minimum on/off times, minimum power etc.)
and the stochastic and multi-stage nature of these problems represent technical barriers. In order to
overcome this challenge it is necessary to develop advanced algorithmic techniques based on reformulation
and decomposition algorithms. In order to be efficient, these techniques will also have to undergo a number
of improvements.
Work description: The first goal of this study will be to gather the state-of-the-art of the latest algorithmic
developments for solving two- and multi-stage stochastic problems with continuous and integer recourse.
For two-stage problems, we will be interested in recent advances in methods based on Benders decomposition
(Rahmaniani et al., 2017), especially stabilization, strategies aiming to balance the information
between the master and subproblems, batching of subproblems (Blanchot et al., 2023), and cut strengthening
(Chen and Luedtke, 2022). We will also study algorithms based on Lagrangian dual decomposition
such as progressive hedging or bundle methods for which the application of strategies like branch-andbound
allow to handle the integer recourse case (Atakan and Sen, 2018; Kim and Dandurand, 2022). For
multi-stage problems, we will be interested in stochastic dual dynamic integer programming (SDDiP) (Zou
et al., 2019) which has been applied to investment problems (Lara et al., 2020) sharing similarities with
the problem studied by EDF.
Using publicly available open-source implementations of the aforementioned techniques (for instance (Kim
and Zavala, 2018)) and implementations that will be developed by the postdoctoral researcher, a numerical
study will be conducted in order to quantify the loss of optimality due to approximations (multi/two-stage
and continuous/integer recourse) on smaller-scale problems having the same structure as the application
at hand. This part of the study will aim to identify the limitations of the existing approaches as well as
determine the most relevant approximation of the target problem.
We will then work on trying to solve the scientific roadblocks determined in the first phase for the most
relevant version of the problem. Improving existing methodologies based on the special structure of the
problem at hand, or developing heuristic version of existing approaches are possible avenues that might
be explored.
Profile: PhD in Operations research or Mathematical optimization.
Required skills:
- Mixed-integer linear programming
- Significant experience with programming languages (C++ preferred)
Skills/knowledge that would be appreciated:
- Decomposition methods in mixed-integer linear programming (Benders, Dantzig-Wolfe, Lagrangian)
- Stochastic programming, robust optimization
- Dynamic programming
- Modeling or solving industrial problems
Salary: ~2,250€/month (net)
Environment: The work will primarily be conducted in the Inria project-team Edge, in the building of the
Mathematics Institute of Bordeaux located at Talence.
There will also be a number of trips to EDF offices (Massy): one to two weeks at the start of the position
and approximately 2 days per month. There may also be one or two trips to Lille. Transport and
accommodation costs for these trips are covered.
References
Atakan, S. and Sen, S. (2018). A progressive hedging based branch-and-bound algorithm for mixed-integer
stochastic programs. Computational Management Science, 15(3-4):501–540.
Blanchot, X., Clautiaux, F., Detienne, B., Froger, A., and Ruiz, M. (2023). The benders by batch algorithm: design
and stabilization of an enhanced algorithm to solve multicut benders reformulation of two-stage stochastic
programs. European Journal of Operational Research, 309(1):202–2016.
Chen, R. and Luedtke, J. (2022). On generating lagrangian cuts for two-stage stochastic integer programs.
INFORMS Journal on Computing, 34(4):2332–2349.
Kim, K. and Dandurand, B. (2022). Scalable branching on dual decomposition of stochastic mixed-integer
programming problems. Mathematical Programming Computation, 14(1):1–41.
Kim, K. and Zavala, V. M. (2018). Algorithmic innovations and software for the dual decomposition method
applied to stochastic mixed-integer programs. Mathematical Programming Computation, 10(2):225–266.
Lara, C. L., Siirola, J. D., and Grossmann, I. E. (2020). Electric power infrastructure planning under uncertainty:
stochastic dual dynamic integer programming (sddip) and parallelization scheme. Optimization and
Engineering, 21(4):1243–1281.
Rahmaniani, R., Crainic, T. G., Gendreau, M., and Rei, W. (2017). The benders decomposition algorithm: A
literature review. European Journal of Operational Research, 259(3):801–817.
Zou, J., Ahmed, S., and Sun, X. A. (2019). Stochastic dual dynamic integer programming. Mathematical
Programming, 175:461–502.
[cid:image001.png@01D9EAF0.93CE6D10]
Cécile Rottner
Ingénieure-chercheure
EDF R&D département OSIRIS
Groupe R36 « Méthodes, modèles et outils d'optimisation »
7 boulevard Gaspard Monge, 91 120 Palaiseau, France
cecile.rottner@edf.fr<mailto:cecile.rottner@edf.fr>
Ce message et toutes les pièces jointes (ci-après le 'Message') sont établis à l'intention exclusive des destinataires et les informations qui y figurent sont strictement confidentielles. Toute utilisation de ce Message non conforme à sa destination, toute diffusion ou toute publication totale ou partielle, est interdite sauf autorisation expresse.
Si vous n'êtes pas le destinataire de ce Message, il vous est interdit de le copier, de le faire suivre, de le divulguer ou d'en utiliser tout ou partie. Si vous avez reçu ce Message par erreur, merci de le supprimer de votre système, ainsi que toutes ses copies, et de n'en garder aucune trace sur quelque support que ce soit. Nous vous remercions également d'en avertir immédiatement l'expéditeur par retour du message.
Il est impossible de garantir que les communications par messagerie électronique arrivent en temps utile, sont sécurisées ou dénuées de toute erreur ou virus.
____________________________________________________
This message and any attachments (the 'Message') are intended solely for the addressees. The information contained in this Message is confidential. Any use of information contained in this Message not in accord with its purpose, any dissemination or disclosure, either whole or partial, is prohibited except formal approval.
If you are not the addressee, you may not copy, forward, disclose or use any part of it. If you have received this message in error, please delete it and all copies from your system and notify the sender immediately by return message.
E-mail communication cannot be guaranteed to be timely secure, error or virus-free.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
