| EPSRC Reference: |
EP/H020454/1 |
| Title: |
Scenario-Free Stochastic Programming |
| Principal Investigator: |
Kuhn, Professor D |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
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: |
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
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
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| 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 |