The Decision Rule Approach to Optimisation under Uncertainty: Theory and Applications
Author(s)
Georghiou, Angelos
Type
Thesis
Abstract
Optimisation under uncertainty has a long and distinguished history in operations research.
Decision-makers realised early on that the failure to account for uncertainty in optimisation
problems can lead to substantial unexpected losses or even infeasible solutions. Therefore,
approximating the uncertain parameters by their average or nominal values may result in
decisions that perform poorly in scenarios that deviate from the average.
For the last sixty years, scenario tree-based stochastic programming has been the method
of choice for solving optimisation problems affected by parameter uncertainty. This method
approximates the random problem parameters by finite scenarios that can be arranged as a
tree. Unfortunately, this approximation suffers from a curse of dimensionality: the tree needs
to branch whenever new uncertainties are revealed, and thus its size grows exponentially with
the number of decision stages.
It has recently been argued that stochastic programs can quite generally be made tractable
by restricting the space of recourse decisions to those that exhibit a linear data dependence.
An attractive feature of this linear decision rule approximation is that it typically leads to
polynomial-time solution schemes. Unfortunately, the simple structure of linear decision rules
sacrifices optimality in return for scalability. The worst-case performance of linear decision
rules is in fact rather disappointing. When applied to two-stage robust optimisation problems
with m linear constraints, the underlying worst-case approximation ratio has been shown to
be of the order O(√m). Therefore, in this thesis we endeavour to construct efficiently computable
instance-wise bounds on the loss of optimality incurred by the linear decision rule
approximation.
The contributions of this thesis are as follows. (i)We develop an efficient algorithm for assessing
the loss of optimality incurred by the linear decision rule approximation. The key idea is to
apply the linear decision rule restriction not only to the primal but also to a dual version of
the stochastic program. Since both problems share a similar structure, both problems can
be solved in polynomial-time. The gap between their optimal values estimates the loss of
optimality incurred by the linear decision rule approximation. (ii) We design an improved
approximation based on non-linear decision rules, which can be useful if the optimality gap of
the linear decision rules is deemed unacceptably high. The idea takes advantage of the fact that one can always map a linearly parameterised non-linear function into a higher dimensional
space, where it can be represented as a linear function. This allows us to utilise the machinery
developed for linear decision rules to produce superior quality approximations that can be
obtained in polynomial time. (iii) We assess the performance of the approximations developed
in two operations management problems: a production planning problem and a supply chain
design problem. We show that near-optimal solutions can be found in problem instances with
many stages and random parameters. We additionally compare the quality of the decision rule
approximation with classical approximation techniques. (iv) We develop a systematic approach
to reformulate multi-stage stochastic programs with a large (possibly infinite) number of stages
as static robust optimisation problem that can be solved with a constraint sampling technique.
The method is motivated via an investment planning problem in the electricity industry.
Decision-makers realised early on that the failure to account for uncertainty in optimisation
problems can lead to substantial unexpected losses or even infeasible solutions. Therefore,
approximating the uncertain parameters by their average or nominal values may result in
decisions that perform poorly in scenarios that deviate from the average.
For the last sixty years, scenario tree-based stochastic programming has been the method
of choice for solving optimisation problems affected by parameter uncertainty. This method
approximates the random problem parameters by finite scenarios that can be arranged as a
tree. Unfortunately, this approximation suffers from a curse of dimensionality: the tree needs
to branch whenever new uncertainties are revealed, and thus its size grows exponentially with
the number of decision stages.
It has recently been argued that stochastic programs can quite generally be made tractable
by restricting the space of recourse decisions to those that exhibit a linear data dependence.
An attractive feature of this linear decision rule approximation is that it typically leads to
polynomial-time solution schemes. Unfortunately, the simple structure of linear decision rules
sacrifices optimality in return for scalability. The worst-case performance of linear decision
rules is in fact rather disappointing. When applied to two-stage robust optimisation problems
with m linear constraints, the underlying worst-case approximation ratio has been shown to
be of the order O(√m). Therefore, in this thesis we endeavour to construct efficiently computable
instance-wise bounds on the loss of optimality incurred by the linear decision rule
approximation.
The contributions of this thesis are as follows. (i)We develop an efficient algorithm for assessing
the loss of optimality incurred by the linear decision rule approximation. The key idea is to
apply the linear decision rule restriction not only to the primal but also to a dual version of
the stochastic program. Since both problems share a similar structure, both problems can
be solved in polynomial-time. The gap between their optimal values estimates the loss of
optimality incurred by the linear decision rule approximation. (ii) We design an improved
approximation based on non-linear decision rules, which can be useful if the optimality gap of
the linear decision rules is deemed unacceptably high. The idea takes advantage of the fact that one can always map a linearly parameterised non-linear function into a higher dimensional
space, where it can be represented as a linear function. This allows us to utilise the machinery
developed for linear decision rules to produce superior quality approximations that can be
obtained in polynomial time. (iii) We assess the performance of the approximations developed
in two operations management problems: a production planning problem and a supply chain
design problem. We show that near-optimal solutions can be found in problem instances with
many stages and random parameters. We additionally compare the quality of the decision rule
approximation with classical approximation techniques. (iv) We develop a systematic approach
to reformulate multi-stage stochastic programs with a large (possibly infinite) number of stages
as static robust optimisation problem that can be solved with a constraint sampling technique.
The method is motivated via an investment planning problem in the electricity industry.
Date Issued
2012-08
Date Awarded
2013-02
Copyright Statement
Attribution NoDerivatives 4.0 International Licence (CC BY-ND)
Advisor
Rustem, Berc
Kuhn, Daniel
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)