Context

This study takes place in the context of a PGMO1 project involving experts in operations research and mathematical programming at LAAS-CNRS, CNAM, ENSTA Paris and EDF. The project addresses the Hydro Unit Commitment (HUC) problem, a challenging subcomponent of the Unit Commitment Problem (UCP) in power generation planning at EDF. The objective is to optimize the scheduling of hydroelectric units to meet demand while maximizing profit and adhering to operational constraints. Its combinatorial complexity and strict volume constraints make it particularly difficult.
The study investigates the physical nonlinearities of HUC, with a focus on the power function of hydroelectric units. This function is continuous but nonlinear (nonconvex and nonconcave), and mainly depends on the water flow and the water height in the upstream reservoir. This naturally leads to model the problem as a mixed-integer non-linear program (MINLP).
MILP-based approximation approaches typically rely on either discretizing the nonlinear power function to generate a set of operating points [1,2] (each defined by a pair of generated power and corresponding water flow) or approximating nonlinear functions using piecewise linear segments [3,4]. The approximation error (AE) of a MILP solution is defined as the relative difference between the optimal MILP solution value and the value obtained by reevaluating the solution with the original nonlinear function. Prior research has demonstrated that piecewise linear approximation-based MILP models can achieve effective trade-offs between computational time and AE [5]. However, the optimal number of linear segments is not always known a priori [3]. As a result, for new problem instances, a trial-and-error approach may be required, limiting the effectiveness of the method.

This internship aims at addressing this limitation by designing an algorithm able to compute piecewise linear functions that approximate nonlinear power functions with the minimum number of pieces given a predefined precision.

Objectives

1) Propose an algorithm to compute the optimal piecewise linear approximation of a nonlinear HUC power function given a bound on the final AE.

2) Study and adapt the source code of the algorithm BORWin inherited from the previous doctoral researcher [2] based on the discretization of operating points

3) Perform numerical tests and compare approaches on real and artificial EDF instances.

Required profile

Master's degree or engineering school in computer science and/or operations research

Duration and organization

Six-month internship starting in February/March 2026.

It will take place in LAAS-CNRS (Toulouse)

Supervising team

The internship will be supervised by researchers from the PGMO project and EDF.

Contact to apply

Sandra Ulrich Ngueveu :

References
[1] Heintzmann, A., Artigues, C., Bendotti, P., Ngueveu, S. U., & Rottner, C. (2023, September). Efficient exact A* algorithm for the single plant Hydro Unit Commitment problem. In 2023 18th Conference on Computer Science and Intelligence Systems (FedCSIS) (pp. 533-543). IEEE.
[2] Heintzmann, A., Models and algorithms for the Hydro Unit Commitment problem, PhD Thesis, Univ. Toulouse, 2024
[3] Heintzmann, A., Artigues, C., Bendotti, P., Ngueveu, S. U., & Rottner, C. (2024). A comparison of alternative models for solving a non-linear single plant Hydro Unit Commitment problem. Computers & Operations Research, 165, 106591.
[4] Ngueveu, S. U., Artigues, C., Absi, N., & Kedad-Sidhoum, S. (2022). Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs. Journal of Heuristics, 28(1), 93-120.
[5] Codsi, J., Ngueveu, S. U., & Gendron, B. (2025). LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization. Mathematical Programming Computation, 17(2), 265-306.