On the Sparsity of Optimal Linear Decision Rules in Robust Inventory Management

We consider the widely-studied class of production-inventory problems from the seminal work of Ben-Tal et al. (2004) on linear decision rules in robust optimization. We prove that there always exists an optimal linear decision rule for this class of problems in which the number of nonzero parameters in the linear decision rule is equal to a small constant times the number of parameters in a static decision rule. This result demonstrates that the celebrated performance of linear decision rules in such robust inventory management problems can be obtained without sacrificing the simplicity of static decision rules. From a practical standpoint, our result lays a theoretical foundation for the growing stream of literature on harnessing sparsity to develop practicable algorithms for computing optimal linear decision rules in operational planning problems with many time periods. Our proof is based on a principled analysis of extreme points of linear programming formulations, and we show that our proof techniques extend to other fundamental classes of robust optimization problems from the literature.