Scenario-Free Stochastic Programming

Completed

Other Cross-Cutting Technologies or Research(Energy system analysis)
Not Energy Related
Other Power and Storage Technologies(Electric power conversion)
Other Power and Storage Technologies(Electricity transmission and distribution)

Basic and strategic applied research

PHYSICAL SCIENCES AND MATHEMATICS (Computer Science and Informatics)

Systems Analysis related to energy R&D

Dr D Kuhn
Computing
Imperial College London

Standard

EPSRC

01 June 2010

31 May 2011

12 months

£99,963

Info. & commun. Technol.

London

NC : ICT

Dr D Kuhn, Computing, Imperial College London

Project Contact, e&t ENERGIE HANDELSGESELLSCHAFT m.b.H, Austria

Stochastic programming is a powerful modelling paradigm for decision problems under uncertainty over time. It has an extremely broad application spectrum, ranging from engineering to economics, logistics, and health care, etc. A typical decision problem under uncertainty is energy investment planning. The operator of a power system has to decide on a technology mix (where to build what types of power plants?) and network topology without knowing the future electricity demand (and its spatial distribution). Stochastic programming techniques can help the system operator to build a reliable power system that provides uninterrupted service in an uncertain environment. Unfortunately, stochastic programming models are often computationally excruciating. The traditional approach to make them amenable to algorithmic solution procedures is to replace the underlying process of random parameters by a finite scenario tree. However, the size of this tree grows exponentially with the number of decision stages, which impedes scalability. Instead of approximating the process of random parameters by scenario trees, one can alternatively approximate the functional form of the 'recourse decisions' or 'decision rules.' So far, only linear decision rules have been studied thoroughly. Unlike scenario tree-based approximations, they lead to tractable (scalable) mathematical models but may incur significant approximation errors. In this project, we plan to elaborate novel scenario-free approaches to stochastic programming, which retain the favourable scalability properties of linear decision rules but provide better approximation quality. In particular, we plan to identify low-parametric classes of non-linear decision rules over which one can optimize in polynomial time and to elaborate a decision rule-based modelling toolbox for stochastic optimization problems. We also intend to develop polynomial-time algorithms which estimate the loss of optimality incurred by decision rule-based approximations and to investigate the inherent trade-off between optimality and scalability. The new techniques and software prototypes will be used to analyse an energy investment planning problem. Modern decision rule-based methods are likely to have a significant impact on the field of stochastic programming as they lead to polynomial-time algorithms and may allow us to solve many societally important, high-dimensional decision problems reliably and quickly.

05/01/10