LAUSR

The “weakly coupled dynamic program” describes a broad class of stochastic optimization problems in which multiple controlled stochastic processes evolve independently but subject to a set of linking constraints imposed on the controls. One feature of the weakly coupled dynamic program is that it decouples into lower dimensional dynamic programs by dualizing the linking constraint via the Lagrangian relaxation, which yields a bound on the optimal value of the original dynamic program. Together with the Lagrangian bound, we generalize the information relaxation approach that relaxes the nonanticipative constraint on the controls to obtain a tighter dual bound. To tackle large-scale problems, we further propose a computationally tractable method based on information relaxation, and show it provides a valid dual bound and its performance has a uniform bound regardless of the number of subproblems. We demonstrate our method on a dynamic product promotion problem.