EPSRC logo

Details of Grant 

EPSRC Reference: EP/H020454/1
Title: Scenario-Free Stochastic Programming
Principal Investigator: Kuhn, Professor D
Other Investigators:
Researcher Co-Investigators:
Project Partners:
e&t Engery Trading Company
Department: Dept of Computing
Organisation: Imperial College London
Scheme: First Grant - Revised 2009
Starts: 01 June 2010 Ends: 31 May 2011 Value (£): 99,963
EPSRC Research Topic Classifications:
Fundamentals of Computing Software Engineering
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
20 Nov 2009 ICT Prioritisation Panel (Nov 09) Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.imperial.ac.uk