Scenario-Free Stochastic Programming

Lead Research Organisation: Imperial College London
Department Name: Dept of Computing

Abstract

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.

Planned Impact

We have identified the following (non-academic) key beneficiaries of the proposed research project: * Energy Producers and Electric Utilities: Important strategic and operational decision problems of energy producers and electric utilities are naturally formulated as stochastic or robust optimization problems, e.g., unit commitment and short-term scheduling of power plants, strategic investment planning and capacity expansion of power systems and transmission networks, the construction and management of an electricity procurement portfolio under risk constraints. Energy producers and utilities can benefit from our novel stochastic programming models to optimize their systems. Our scenario-free approaches will allow them to solve more realistic models within the time constraints dictated by operational requirements. * Energy Consumers: The general public benefits from higher reliability of service and a more sustainable use of natural resources if energy companies employ uncertainty-immunized (robust) planning and scheduling models. * Chemical Process Industry: Many important decision problems in the chemical process industry require stochastic optimization-based solution approaches, e.g., production planning, scheduling, design of chemical processing systems, melt control, blending problems, and supply chain management, etc. As there are substantial uncertainties concerning the availability of resources, the prices and demands of products, the reliability and availability of plants or machines, etc., optimization models thus have to be robustified against model uncertainties. * Automotive and Aerospace Industries: Feedback control systems are ubiquitous in modern technological life. Robust and stochastic controllers are needed in applications to flight simulation of new autopilots, control of spacecrafts, uninhabited vehicles, aircrafts, and helicopters, etc. The optimal controller design can be formulated as a stochastic or robust optimization problem in the spirit of the proposed research project. The graceful scalability properties of our novel scenario-free solution procedures may enable real-time online optimization of control systems, thereby significantly enhancing their effectiveness. A variety of mechanisms will ensure that our project partner e&t as well as other potential users and beneficiaries of the outcomes of this project will be engaged at an early stage in the knowledge transfer and tool development. * Case Study: Our project partner e&t will provide data for a case study. Within this case study we plan to evaluate the benefits of scenario-free stochastic optimization techniques for the planning and operation of power systems. * Workshop for Energy Professionals: e&t has also agreed to organize a workshop in which the project team will have the opportunity to present the key results of the proposed research project to an audience of industrial decision-makers and energy professionals. The workshop will take place in Vienna at the end of the project period. * CPSE Consortium Meetings: Dissemination of the research outcomes to the chemical process industry will be through the industrial consortium meetings of the Centre for Process Systems Engineering (CPSE). CPSE is an interdisciplinary research center with the mission to develop expertise over the whole range of process systems engineering and to develop mechanisms for the transfer of new technology to industry. * If specific software tools developed during the project turn out to be suitable for commercialization, we envisage a collaboration with Imperial Innovations, one of the UK's leading technology transfer companies associated with Imperial College London.

Publications

10 25 50
 
Description Stochastic programming is a powerful modelling paradigm for decision problems under uncertainty. It has an extremely broad application spectrum, ranging from engineering to economics, logistics, and health care, etc. 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 often 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 mathematical models but may incur significant approximation errors.



In this project we have developed an efficient method to measure the degree of suboptimality of the best linear decision rule. Our method is generic and applies to a large class of linear and quadratic stochastic programs. If this method indicates that the loss of optimality is substantial for a particular problem instance, then the use of linear decision rules is not appropriate. To improve the approximation quality of linear decision rules, we have identified low-parametric classes of non-linear decision rules which retain the favourable scalability properties of linear decision rules but provide better approximation quality. In particular, we have studied piecewise linear and polynomial decision rules. With the help from graduating MEng students from the Department of Computing at Imperial College we have further designed and implemented a software prototype which employs decision rule-based approximations for automatically translating user-specified decision problems into tractable mathematical programs that can be solved with off-the-shelf optimisation software. The work by Caroline Anjorin in this domain was rewarded with the IBM project prize of the Department of Computing (http://www.doc.ic.ac.uk/teaching/distinguished-projects/2010/c.anjorin.pdf).



We have applied the new modelling techniques and software prototypes to several decision problems of practical relevance: energy procurement portolio management and scheduling of hydro power plants (in collaboration with our project partner e&t), stochastic vehicle routing (in collaboration with the Computer-Aided Systems Laboratory, Princeton University), infrastructure and production planning in offshore oilfields (in collaboration with the Centre for Process Systems

Engineering, Imperial College and UCL), hedging of energy derivatives in incomplete markets, and scheduling of multi-class queuing networks. In all of these application areas the new decision rule techniques have outperformed the established methodologies significantly.



This project showed that the scalable decision rule-based approximation methods under investigation promise to open up new application areas for stochastic programming and are thus beneficial for a wide range of academic and industrial modelers in various areas.