Constructive dynamic programming with applications in electric power system operation

Many important problems faced in large infrastructure systems, such as the electricityindustry, involve the optimisation of complex processes over many stages. Often, theseproblems require resolving in response to unpredicted changes in system state duringreal-time operation. In conjunction, the restructuring of these industries around theworld has led to a greater need for fast and efficient optimisation techniques that providetransparent solutions. Such transparency is provided by dual variables in optimisationproblems that illuminate the underlying mechanisms driving costs.This thesis presents a new, exact, and non-iterative method of optimising staged systemstermed Constructive Dynamic Programming. The method is applicable to systems thatcan be modelled by the sum of a sequence of polyhedral (piecewise-linear convex) costfunctions and that are subject to linear constraints within and between consecutivestages. The problem is formulated as a dynamic program and a variant of parametricprogramming is used to solve the single-stage subproblem exactly. Optimalityconditions are expressed using the subdifferential operator of convex analysis and canbe interpreted as finding combinations of multipliers in the vector space of dualvariables. Complete primal and dual information for all continuous system states isavailable for every stage, conveying information on marginal costs of variables andshadow costs of constraints. The technique allows rapid determination of optimaloperation following unexpected changes in system state.Issues regarding the exact and approximate implementation of the technique arediscussed. Two applications are presented for problems arising in the electricityindustry: dynamic dispatch, determining the output of large inflexible generating unitsover time, and hydrothermal scheduling, coordinating generation owing to hydroelectricreservoir releases with generation from thermal units. Hypothetical examplesare used to illustrate how the technique can be used to study the underlying costs drivingoperating decisions. Both exact and approximate implementations are studied and theircomputational performance compared