  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.
