Transformer-based Stagewise Decomposition for Large-Scale Multistage
  Stochastic Optimization
Chanyeong Kim Jongwoong Park Hyunglip Bae Woo Chang Kim
Solving large-scale multistage stochastic programming (MSP) problems poses a
significant challenge as commonly used stagewise decomposition algorithms,
including stochastic dual dynamic programming (SDDP), face growing time
complexity as the subproblem size and problem count increase. Traditional
approaches approximate the value functions as piecewise linear convex functions
by incrementally accumulating subgradient cutting planes from the primal and
dual solutions of stagewise subproblems. Recognizing these limitations, we
introduce TranSDDP, a novel Transformer-based stagewise decomposition
algorithm. This innovative approach leverages the structural advantages of the
Transformer model, implementing a sequential method for integrating subgradient
cutting planes to approximate the value function. Through our numerical
experiments, we affirm TranSDDP's effectiveness in addressing MSP problems. It
efficiently generates a piecewise linear approximation for the value function,
significantly reducing computation time while preserving solution quality, thus
marking a promising progression in the treatment of large-scale multistage
stochastic programming problems.