Relaxations of Approximate Linear Programs for the Real Option Management of Commodity Storage

The real option management of commodity conversion assets gives rise to intractable Markov decision processes (MDPs), in part because of the use of high-dimensional models of commodity forward curve evolution, as commonly done in practice. Focusing on commodity storage, we identify a deficiency of approximate linear programming (ALP), which we address by developing a novel approach to derive relaxations of approximate linear programs. We apply our approach to obtain a class of tractable ALP relaxations, also subsuming an existing method. We provide theoretical support for the use of these ALP relaxations rather than their associated approximate linear programs. Applied to existing natural gas storage instances, our ALP relaxations significantly outperform their corresponding approximate linear programs. Our best ALP relaxation is both near optimal and competitive with, albeit slower than, state-of-the-art methods for computing heuristic policies and lower bounds on the value of commodity storage, but is more directly applicable for dual (upper) bound estimation than these methods. Our approach is potentially relevant for the approximate solution of MDPs that arise in the real option management of other commodity conversion assets, as well as the valuation of real and financial options that depend on forward curve dynamics. This paper was accepted by Dimitris Bertsimas, optimization.