Given a mix of power plants, the Unit Commitment problem (UC) can be succinctly stated as finding a generation scheduling attending to the following principles:
the produced power needs to match well enough the physical (customer) load;
all operational constraints are satisfied;
ancillary services are provided in a satisfactory manner, and
power is generated at minimal cost.
This easily stated problem is in fact very difficult to model and solve (in particular for EDF), mainly for the following reasons:
the number of generating units is very large;
the load and safety (reserve) requirements couple all units together;
operational constraints are very detailed, and involve relations that can be non-convex and/or of combinatorial nature;
for the computational tool to be useful in practice, its solution times must be "unreasonably" small, when compared to the scale and complexity of the optimization problem.
In this project, we will focus on two forms of UC. The first, "traditional" one (TUC), determines one day ahead a generation plan with minimal production and start-up costs, and which satisfies the physical customer load, as well as certain reserve and system service constraints. The TUC output is a reference planning for the next day. The second problem is the intra-day UC (IUC), solved once every hour, to determine a generation that deviates the least from the planned generation, taking into account the actual realization of uncertainty in the considered hour. Deviation must be minimal in the sense that only a limited number of (groups of) units can modify their generation output on a short notice.
Both UC variants above are useful, not only in themselves as steps of the actual operational planning, but also as sub-models of the "real" UC problem. This is a stochastic program that can be modelled as a problem with recourse, as follows. Having the reference schedule, corrective decisions (the "recourse") can be taken to adapt the planned generation to last minute changes dictated by a given realization of uncertainty, for example, the actual renewable generation or the actual demand of power in the next hour. In this context, TUC outputs the reference schedule (here-and-now decisions) while IUC provides the recourse decisions for any given scenario.
The solution process is currently subdivided in two phases:
Dual Phase: linking constraints are relaxed and a dual problem is maximized, with objective function
Primal Phase: in order to compute a primal feasible (hopefully, good) solution, an augmented dual function is used, which would lead to a non-separable problem; to uncouple variables the auxiliary problem principle is used, and the dual variable is be updated as in Uzawa's method. This scheme is easy to implement, and the augmented dual function values decrease at each iteration; however, convergence to an optimal solution of depends on convexity, which does not hold in practice. Furthermore, concerning the practical behavior of the procedure, it is observed that:
The process converges very slowly.
To ensure feasibility, a "fake" unit is added which can produce any required amount of power at a high cost. For a small perturbation of the load the reported solution should not deviate much in the objective function, however in practice this often happens, indicating that the method is unstable.
Occasionally, the returned solution can be manually improved to yield a feasible solution that better meets load.
The impact of the fact that the subproblems cannot be solved to optimality is not well understood (not even in the convex setting, which is not the case).
The dual signal is actually used in practice for several purposes, e.g. to estimate the marginal cost of units. However, often the dual signal is not sufficiently realistic; in particular, it does not "agree" with the schedule produced by the procedure. This is partly due to the inherent non-convexity of the problem, which does not guarantee the existence of "perfect" dual information, and partly to the fact that the subproblems are modeled in a simplified manner. However, from the operational viewpoint this is an important issue: a signal "explaining perfectly" the primal solution produced by the approach is most desirable.
From the above, we can conclude that the current approach is not always satisfactory. In particular, the method in the Primal Phase is too slow, rather unstable and provides a primal solution that is not consistent with the obtained dual signal.
This project will address the issues above, keeping in mind that there is a trade-off to be found between accuracy and computational speed. Specifically, for optimization problems as complex as the real-life UC problems solved by EdF, it is unreasonable to expect gains on all the fronts. The ultimate goal of this collaboration is indeed to develop a computational tool that produces fast a primal feasible solution together with a consistent dual signal. This is an ambitious objective, difficult to achieve, since it may very well happen that to improve feasibility of the primal solutions, the overall computational time needs to be substantially increased. Also, it is possible that, due to the presence of nonconvex/combinatorial relations, an increase in primal feasibility is accompanied by a deterioration in the quality of the dual signal.
Having said that, the project team counts with a vast know-how and experience in the domain, which made it possible to identify several improvements to the current approach, essentially related to three key topics:
Primal Heuristics during the Dual Phase. The goal of this step is to exit the Dual Phase already with a primal feasible solution.
Improvements in the Primal Phase. To avoid instability, the Primal Phase can be modified, to produce a better dual signal.
Better (Primal and) Dual Phase. While the current Dual Phase is fast and effective, this is so because the (hydro) subproblems are overly simplistic. When subproblems have their "true form", a number of algorithmic improvements to Bundle methods (inexact or disaggregate models, specialized models for some components, modifications to the stabilizing term such as using piecewise-linear functions or proximal levels) can be incorporated, to obtain an overall efficient approach.