  Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve
in general. Linear decision rules (LDRs) yield an approximation of an MSLP by
restricting the decisions at each stage to be an affine function of the
observed uncertain parameters. Finding an optimal LDR is a static optimization
problem that provides an upper bound on the optimal value of the MSLP, and,
under certain assumptions, can be formulated as an explicit linear program.
Similarly, as proposed by Kuhn, Wiesemann, and Georghiou (Math. Program., 130,
177-209, 2011) a lower bound for an MSLP can be obtained by restricting
decisions in the dual of the MSLP to follow an LDR. We propose a new
approximation approach for MSLPs, two-stage LDRs. The idea is to require only
the state variables in an MSLP to follow an LDR, which is sufficient to obtain
an approximation of an MSLP that is a two-stage stochastic linear program
(2SLP). We similarly propose to apply LDR only to a subset of the variables in
the dual of the MSLP, which yields a 2SLP approximation of the dual that
provides a lower bound on the optimal value of the MSLP. Although solving the
corresponding 2SLP approximations exactly is intractable in general, we
investigate how approximate solution approaches that have been developed for
solving 2SLP can be applied to solve these approximation problems, and derive
statistical upper and lower bounds on the optimal value of the MSLP. In
addition to potentially yielding better policies and bounds, this approach
requires many fewer assumptions than are required to obtain an explicit
reformulation when using the standard static LDR approach. A computational
study on two example problems demonstrates that using a two-stage LDR can yield
significantly better primal policies and modestly better dual policies than
using policies based on a static LDR.
