Primal-Dual Aggregation and Disaggregation for Stochastic Linear Programs

A multistage stochastic linear program can be approximated by replacing the underlying information structure by a coarser structure. Given the ordinary Lagrangian for the original problem, this amounts to restricting both the primal and dual variables to be adapted to the coarser information structure. The resulting primal problem has the same form as the original, but with aggregated constraints and decisions. Mutual upper and lower bounds on the optimal values of the original and aggregated problems are obtained via partially aggregated problems formed by restricting only the primal variables or only the dual variables to the coarser structure. The introduction of the partially aggregated problems leads to a general disaggregation framework for developing heuristic approaches to solving the original problem.