Relaxations of Approximate Linear Programs for the Real Option Management of Commodity Storage, Working paper, Carnegie Mellon Univ., 2012

The real option management of commodity conversion assets gives rise to intractable Markov decision pro-cesses (MDPs). This intractability is due primarily to the high dimensionality of a commodity forward curve, which is part of the MDP state when using high dimensional models of the evolution of this curve, as commonly done in practice. Focusing on commodity storage, we develop a novel approximate dynamic programming approach to obtain value function approximations from tractable relaxations of approximate linear programs (ALPs). We derive performance bounds that provide theoretical support for the use of some of these ALP relaxations rather than their respective ALPs. We estimate lower bounds and dual upper bounds on the value of an optimal policy on existing natural gas storage instances using the value function approximation from each of our models. Our ALP relaxations significantly outperform their corresponding ALPs in terms of both the estimated lower and upper bounds. Our approach is also relevant for the approx-imate solution of MDPs that arise in the real option management of other commodity conversion assets, as well as the valuation and management of real and financial options that depend on forward curve dynamics.