Stage EDF R&D - Evaluation and Development of Decomposition Methods to Solve Unit Commitment Problems

Description

Context

The Unit Commitment Problem (UCP) [1] is a ubiquitous issue at EDF, appearing in numerous business applications, and across different temporal and geographical horizons. The UCP is a complex problem for several reasons:

·       Heterogeneity of production units and their constraints,

·       Combinatorial nature of decision variables (on/off decisions, minimum time, etc.),

·       Non-linear nature of certain parameters (production costs, efficiencies, etc.),

·       Large size: large number of production units, large number of time steps,

·       Stochastic nature: depending on the time horizons, different types of uncertainties affect the UCP (renewable energy production quantities, hydraulic stocks, consumption curve, availability of production assets, etc.)

The main challenge is therefore to solve the UCP in a reasonable time while maintaining a level of modeling detail suitable for the needs of the tools used in production. It is crucial to have a set of varied and state-of-the-art methods to model and solve it efficiently. Several approaches exist in the scientific literature on this subject, including approaches based on temporal and geographical decompositions of the basic problem.

Internship Objectives

The objective of the internship will be to develop and compare decomposition methods (splitting methods) [2] based on algorithms such as ADMM (Alternative Decomposition Method of Multipliers) [3,4,5]. A Python library that facilitates the generation of various production parks for UCP optimization, along with resolution classes implementing different types of ADMM-based algorithms, is already being developed internally.

The internship has two main goals. Firstly, it aims to propose other ADMM-based algorithms that seem relevant (in a sense to be explored) with respect to the typical problems to be solved. Secondly, it aims to implement these algorithms in this library and conduct a thorough benchmarking of the different methods developed. A publication may be considered depending on the quality of the results obtained.

More specifically, the intern will be required to perform the following tasks:

-       Conduct a literature review on ADMM-type decomposition methods.

-       Propose different variants of ADMM to apply to the UCP (starting with the convex version and then the non-convex version). Indeed, from a decomposition method, there are several ways to apply it with practical performances that can be significant industrially (e.g., the same decomposition method can practically result in two different algorithms [6,7]).

-       Implement these methods in the developed Python library and test them on different problems. 

Practical Points

Internship Location: EDF Lab Paris-Saclay (7, Boulevard Gaspard Monge; 91120 Palaiseau). The site is accessible by public transport and via an EDF shuttle.

Duration: 6 months.

Compensation: Internships are remunerated based on the level of study and the training being prepared.

Intern Profile: Engineering school or research master’s degree, master’s level.

Areas of Expertise: Master’s with a specialization in optimization (with a foundation in convex optimization), software development.

Application: Applications (cover letter and CV) should be sent directly to the supervisors.

Antoine Bambade

antoine.bambade@edf.fr

Mehdi Charles

mehdi.charles@edf.fr

Adrien Séguret

adrien.seguret@edf.fr

Bibliography

[1] Tahanan, M., van Ackooij, W., Frangioni, A., & Lacalandra, F. (2015). Large-scale unit commitment under uncertainty. 4or, 13, 115-171.

[2] Jonathan Eckstein. Splitting methods for monotone operators with applications to parallel optimization. PhD thesis, Massachusetts Institute of Technology, 1989.

[3] Michel Fortin and Roland Glowinski. Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems. Elsevier, 2000.
 [4] Daniel Gabay. applications of the method of multipliers to variational inequalities. In Studies in mathematics and its applications, volume 15, pages 299–331. Elsevier, 1983.
 [5] Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & mathematics with applications, 2(1):17–40, 1976

[6] Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization
 via operator splitting and homogeneous self-dual embedding. Journal of Optimization
 Theory and Applications, 169(3):1042–1068, June 2016.

[7] B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathematical Programming Computation, 12(4):637–672, 2020