A portfolio of purchase contracts – an example of solving large-scale dynamic programming on parallel computers

The curse of dimensionality means that, though many stochastic sequential decision problems can be modelled as dynamic-programming problems, their memory requirements and large solution times make them impracticable to solve on most serial computers. This paper looks at an example of such a problem – the optimal portfolio of purchase contracts – which was solved using a parallel computer and a LAN of workstations. It concentrates on two questions related to the solution of this problem. (1) What are the factors of problem formulation and solution computation that make the problem solvable in reasonable time? (2) What advantage, if any, does the stochastic model – a Markov decision process – of the problem have over a deterministic approximate model, given that the latter leads to a ‘simpler’ model?