On the Sparsity of Optimal Linear Decision Rules in Robust Optimization

We consider the widely-studied class of production-inventory problems with box uncertainty sets 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 grows linearly in the number of time periods. This is the first result to prove that optimal linear decision rules are sparse in a widely-studied class of robust optimization problems with many time periods. Harnessing this sparsity guarantee, we introduce a novel reformulation technique that allows robust optimization problems such as production-inventory problems to be solved as a compact linear optimization problem when most of the parameters of the linear decision rules are forced to be equal to zero. We also develop an active set method for identifying the parameters of linear decision rules that are equal to zero at optimality. In numerical experiments on production-inventory problems with hundreds of time periods, we find that our novel reformulation technique coupled with the active set method yield more than a 32x speedup over state-of-the-art linear optimization solvers in computing linear decision rules that are within 1% of optimal. Our proofs and algorithms are based on a principled analysis of extreme points of linear optimization formulations, and we show that our sparsity guarantees extend to other widely-studied classes of robust optimization problems from the literature.