The Decision Rule Approach to Optimisation under Uncertainty: Theory and Applications

摘要

Optimisation under uncertainty has a long and distinguished history in operations research.udDecision-makers realised early on that the failure to account for uncertainty in optimisationudproblems can lead to substantial unexpected losses or even infeasible solutions. Therefore,udapproximating the uncertain parameters by their average or nominal values may result inuddecisions that perform poorly in scenarios that deviate from the average.udFor the last sixty years, scenario tree-based stochastic programming has been the methodudof choice for solving optimisation problems affected by parameter uncertainty. This methodudapproximates the random problem parameters by finite scenarios that can be arranged as audtree. Unfortunately, this approximation suffers from a curse of dimensionality: the tree needsudto branch whenever new uncertainties are revealed, and thus its size grows exponentially withudthe number of decision stages.udIt has recently been argued that stochastic programs can quite generally be made tractableudby restricting the space of recourse decisions to those that exhibit a linear data dependence.udAn attractive feature of this linear decision rule approximation is that it typically leads toudpolynomial-time solution schemes. Unfortunately, the simple structure of linear decision rulesudsacrifices optimality in return for scalability. The worst-case performance of linear decisionudrules is in fact rather disappointing. When applied to two-stage robust optimisation problemsudwith m linear constraints, the underlying worst-case approximation ratio has been shown toudbe of the order O(√m). Therefore, in this thesis we endeavour to construct efficiently computableudinstance-wise bounds on the loss of optimality incurred by the linear decision ruleudapproximation.udThe contributions of this thesis are as follows. (i)We develop an efficient algorithm for assessingudthe loss of optimality incurred by the linear decision rule approximation. The key idea is toudapply the linear decision rule restriction not only to the primal but also to a dual version ofudthe stochastic program. Since both problems share a similar structure, both problems canudbe solved in polynomial-time. The gap between their optimal values estimates the loss ofudoptimality incurred by the linear decision rule approximation. (ii) We design an improvedudapproximation based on non-linear decision rules, which can be useful if the optimality gap ofudthe 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 dimensionaludspace, where it can be represented as a linear function. This allows us to utilise the machineryuddeveloped for linear decision rules to produce superior quality approximations that can beudobtained in polynomial time. (iii) We assess the performance of the approximations developedudin two operations management problems: a production planning problem and a supply chainuddesign problem. We show that near-optimal solutions can be found in problem instances withudmany stages and random parameters. We additionally compare the quality of the decision ruleudapproximation with classical approximation techniques. (iv) We develop a systematic approachudto reformulate multi-stage stochastic programs with a large (possibly infinite) number of stagesudas static robust optimisation problem that can be solved with a constraint sampling technique.udThe method is motivated via an investment planning problem in the electricity industry.