by Claude Lemaréchal
After fifteen years of collaboration, EdF, the French Electricity Board and INRIA are finalising an efficient software which will optimise the daily production of electricity in France.
To meet a demand that oscillates between 40 and 60 gigawatts, EdF operates about 150 thermal units (nuclear and conventional) and 50 hydro-valleys. Since electricity can hardly be stored, production must closely follow demand. Changing the operation mode of a unit however, especially a thermal one, is difficult and costly. As a result, optimising the schedules is a critical problem, involving large amounts of money. It is also a tough nut to crack, and is often referred to as the unit-commitment problem: large-scale, mixed-integer, heterogeneous. Its complexity can be illustrated by a superficial description of the production units.
|Barrage de Chaudanne, a hydro-valley operated by EDF, the French electicity board.
Photo by Dr. Klaus Janberg.
A thermal unit must produce a certain minimum power (positive). This introduces a combinatorial aspect into its operation - the unit is 'on' or 'off'. This is not the only one, however: when switched off or on, the unit must respectively stay off or maintain its production level, for a minimum period of time. Also, when switching on, the unit must follow specific start-up curves that depend, among other things, on how long the unit has been off. Many similar constraints exist, and we will not enumerate them here. Thermal plants can be suitably modelled such that the resulting optimisation problem would be tractable if there were only one unit to meet the demand - but this is certainly not the case with 150.
A hydro-valley is a set of interconnected reservoirs and associated power plants, each of which has a certain number of turbines. Some plants are equipped to pump water from their downstream reservoir into their upstream reservoir (thus allowing this water to be reused later during peak hours), but a plant cannot simultaneously discharge (producing energy) and pump (consuming energy). Using convenient simplifying assumptions, hydro-valleys can be modelled as an ordinary linear programming problem, which is once again easy to solve with one valley, but not with fifty.
One way of tackling the unit-commitment problem is price decomposition: the constraint of meeting demand is replaced by a 'dummy benefit' rewarding each megawatt produced by a unit (the marginal benefit is the same for all units). This replacement, called Lagrangian relaxation, allows a separate optimisation of the 150+50 production units. As a result, we are faced with a coordination problem, which is to find optimal dummy prices. Since October 2002, EdF has been using the so-called bundle method, which was invented at INRIA in the mid-seventies, and which is particularly efficient for this sort of problem.
The question then arises: can it be guaranteed that coordination produces equilibrium? The answer is a definite 'no' - the schedules computed by Lagrangian relaxation are far from meeting demand within acceptable tolerances. While a certain combination of them does meet it, this does not produce a technically feasible schedule.
To balance these two opposite outputs, a heuristic technique has been developed, also at INRIA, and is now being industrially evaluated by EdF. Experiments on real datasets indicate that substantial gains are obtained, as compared to the implementation currently in operation at EdF. In fact, the coordination phase delivers not only optimal dummy prices, but also a lower bound on the minimum possible cost of any feasible schedule; this is a well-known property of Lagrangian relaxation. Usually, the feasible schedules produced by the current implementation cost about 1% more than this lower bound. The new approach typically cuts this excess by a half.
However, the main advantage of the new approach is its robustness, which can be illustrated as follows. On a particular day in 2002, an uncommon peak load of 70GW occurred. The schedule obtained by the current implementation produced an intolerable mismatch of 1.3GW; in contrast, the new heuristic technique managed to find a schedule that cost less and, more importantly, met the demand to within 50MW - quite a reasonable tolerance.
Claude Lemaréchal, INRIA
Tel: +33 04 76 61 52 02