Modeling and Optimizing Energy in a
Stochastic Environment :

From Aggregate Mid Term
Planning to On-line Scheduling

CHRISTINE LÜTOLF
Ecole Polytechnique Fédérale de Lausanne
Département de Mathématiques
CH - 1015 Lausanne

Electricity demand of households and industry is still growing as fast as ever. The opening of energy markets worldwide and the ensuing sharp competition add new challenges for planners. Indeed, their decisions must be made under stringent time pressure in an environment that has become more complex and volatile.

This thesis addresses problems arising  in on-line, short and mid term electricity production planning in a stochastic environment. The approach used is general, also applicable to other problems of planning under uncertainty.

Energy planning is concerned with finding a least-cost schedule for the components of a given power system, such as satisfying demand and taking into account, e.g., start-up and production costs, minimum operating periods, capacity limits, and reliability requirements. Decisions are often due before the demand is known, and planning is based on forecasts subject to a substantial degree of uncertainty. However, only those decisions concerning the first few periods are actually implemented. In view of this, we propose a method in which a detailed schedule is established for immediate time periods, and at the same time, aggregate decisions are computed for the future. Our approach is an original way to reduce the complexity and size of the large-scale linear mixed-integer problems under consideration, making it possible to take into account stochasticity. Modeling the uncertainty of the demand with scenarios, we describe a method to produce possible future outcomes according to a probability distribution. The short term problem is solved in a Lagrangian relaxation setting and mixed-integer solutions are produced by combining the volume algorithm, a variant of the subgradient algorithm, with a simple rounding heuristic. Guided by the planned schedule, on-line dispatching is the art of deciding between reactive and deliberative planning, least-cost or reserve-first strategies to satisfy the demand in real-time.

A geometric problem, called the extended convex hull problem, which arises in the context of aggregation, is that of computing the convex hull of the union of several d-dimensional polytopes given by inequality descriptions. Our method applies the reverse search algorithm to a shelling ordering of the output facets. Efficient wrapping is done by projecting the polytopes onto the two-dimensional space and solving a linear program. The resulting algorithm is polynomial in the sizes of input and output under the general position assumption.

For further information, please contact Professor Tom Liebling  (thomas.liebling@epfl.ch).