Post-Doctoral Research Visit F/M Decomposition algorithms for solving generation expansion planning problems

The work to be carried out is part of a challenge between Inria and EDF and entitled "Managing tomorrow's power systems".

The work will primarily be conducted in the Inria project-team Edge (Inria centre at the University of Bordeaux), in the building of the Mathematics Institute of Bordeaux located at Talence. The new recruit will work alongside Ayse Arslan, Boris Detienne and Aurélien Froger.

There will be a number of trips to EDF offices located at Massy to work with Cécile Rottner et Rodolphe Griset. These will take place at the start of the position (one to two weeks) and approximately two days per month. There may also be one or two trips to Lille to work with Bernard Fortz and Frédéric Semet. Please note that transport and accommodation costs for these trips are covered.

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 invest- ment 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.

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-and-bound 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.

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.

Gather the state of the art in the latest algorithmic developments for solving two- and multi-stage stochastic problems with continuous and integer recourse

Conduct a numerical study in order to quantify the loss of optimality due to approximations using of publicly available open-source implementations of the most efficient techniques

Design and implement models and algorithms (exact or heuristic) to solve the most relevant version of the problem addressed by EDF

Write scientific reports and articles

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

• Subsidized meals
• Partial reimbursement of public transport costs
• Possibility of teleworking and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

2788€ / month (before taxs)