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.