  Multistage stochastic programs can be approximated by restricting policies to
follow decision rules. Directly applying this idea to problems with integer
decisions is difficult because of the need for decision rules that lead to
integral decisions. In this work, we introduce Lagrangian dual decision rules
(LDDRs) for multistage stochastic mixed-integer programming (MSMIP) which
overcome this difficulty by applying decision rules in a Lagrangian dual of the
MSMIP. We propose two new bounding techniques based on stagewise (SW) and
nonanticipative (NA) Lagrangian duals where the Lagrangian multiplier policies
are restricted by LDDRs. We demonstrate how the solutions from these duals can
be used to drive primal policies. Our proposal requires fewer assumptions than
most existing MSMIP methods. We compare the theoretical strength of the
restricted duals and show that the restricted NA dual can provide relaxation
bounds at least as good as the ones obtained by the restricted SW dual. In our
numerical study on two problem classes, one traditional and one novel, we
observe that the proposed LDDR approaches yield significant optimality gap
reductions compared to existing general-purpose bounding methods for MSMIP
problems.
