Technical Summary: Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization

1. Problem Statement

The paper addresses the computational challenges inherent in solving Large-Scale Multistage Stochastic Programming (MSP) problems. While MSP is effective for sequential decision-making under uncertainty (e.g., production optimization, asset liability management), it suffers from the "curse of dimensionality." As the number of stages and scenario nodes increases, the deterministic equivalent problem becomes computationally intractable.

Existing decomposition methods, particularly Stochastic Dual Dynamic Programming (SDDP), approximate the value function using piecewise linear convex functions constructed by incrementally accumulating subgradient cutting planes. While SDDP guarantees convergence, its computational time grows monotonically with each iteration because the size of the piecewise linear approximation increases as more cuts are added. Furthermore, traditional SDDP requires solving the problem from scratch for every new instance, lacking the ability to generalize across a family of related problems.

2. Methodology: TranSDDP

The authors propose TranSDDP, a novel algorithm that leverages Transformer architectures to generate subgradient cutting planes for approximating the value function in SDDP.

Core Concept

Instead of iteratively solving subproblems to generate cuts one by one, TranSDDP treats the generation of cutting planes as a sequence modeling task. It utilizes a Transformer-based encoder-decoder framework to learn the mapping from problem parameters to a sequence of cuts that approximate the value function.

Model Architecture

• Input Sequence: The model takes a set of parameters defining the probability distributions of the stochastic elements ($\xi_t$) in the feasible region constraints (matrices $A_t, B_t$ and vector $b_t$). These parameters are sampled from a prior distribution to represent a parametric family of problems.
• Output Sequence: The decoder generates a sequence of parameters representing the cuts: gradients ($\tilde{\beta}_k$), intercepts ($\tilde{\alpha}_k$), and category tokens ($\tilde{\tau}_k$) indicating the position in the sequence (start, middle, end, or padding).
• Adaptations: The standard Transformer architecture is modified to handle continuous input and output sequences. The input embedding is replaced with linear layers, and the softmax layer is applied only to the category tokens. A variant, TranSDDP-Decoder, utilizes only the decoder component, as the authors found self-attention on the fixed-size input parameters offered diminishing returns.

Learning System

• Data Generation: The training dataset is constructed by running standard SDDP on various problem instances sampled from the parametric family. The resulting cuts serve as the ground truth.
• Loss Function: The model is trained to minimize a combined loss of Mean Squared Error (MSE) for the continuous cut parameters ($\beta, \alpha$) and Cross-Entropy (CE) for the discrete category tokens ($\tau$).
• Teacher Forcing: During training, the decoder receives the true target sequence (shifted by one step) rather than its own predictions to stabilize learning.
• Initialization: The generation process is initiated with a "trivial cut" (e.g., $\theta \ge 0$) as the first element, mimicking the standard SDDP initialization.

3. Key Contributions

1. First Application of Transformers in MSP: The paper introduces the first investigation of Transformer-based value function approximation specifically within the domain of Multistage Stochastic Programming, distinguishing it from Reinforcement Learning applications.
2. Sequential Cut Generation: Unlike previous neural approaches (e.g., $\nu$-SDDP) that generate a fixed number of cuts based solely on a problem context vector, TranSDDP generates cuts sequentially. This allows the model to consider previously generated cuts when producing new ones, capturing the iterative nature of SDDP more effectively.
3. Generalization and Efficiency: The model learns to generate cuts for a family of problems. Once trained, it can approximate the value function for new problem instances within that family without re-solving the optimization problem from scratch, significantly reducing evaluation time.
4. Handling Non-Linearity: The proposed method successfully handles non-linear convex optimization problems (e.g., financial planning), where previous neural approaches like $\nu$-SDDP were limited to linear programs.

4. Experimental Results

The authors evaluated TranSDDP and TranSDDP-Decoder on three benchmark problems: Energy Planning, Financial Planning, and Production Planning, with 7 and 10 stages.

• Solution Quality:
  • TranSDDP models achieved error ratios comparable to or better than standard SDDP and the Level 1 dominance (L1) heuristic.
  • In Energy Planning, TranSDDP-Decoder achieved an error ratio of 1.01% (7-stage) and ~3.8% (10-stage), outperforming standard SDDP (3.3% and ~3.4%).
  • In Financial Planning, TranSDDP-Decoder significantly outperformed SDDP (0.61% vs 1.78% error for 7-stage).
  • The models generally underperformed compared to VFGL (Value Function Gradient Learning) in specific metrics but offered superior robustness and applicability to non-linear cases where $\nu$-SDDP failed.
• Computational Time:
  • Evaluation Time: TranSDDP demonstrated a massive reduction in evaluation time (seconds) compared to SDDP (minutes to hours). For example, in Energy Planning, evaluation time dropped from ~183s (SDDP) to ~1.99s (TranSDDP).
  • Scalability: While traditional methods' total computational time scales linearly with the number of problems to be solved, TranSDDP's total time remains nearly constant after the initial training phase, making it highly efficient for solving large batches of related problems.
• Feasibility: The models initially generated infeasible cuts during early training epochs, but the infeasibility ratio converged to zero as training progressed, ensuring the final solutions satisfy constraints.

5. Significance and Claims

The paper claims that TranSDDP represents a "promising progression" in treating large-scale MSP problems. Its primary significance lies in:

• Overcoming the "Re-solving" Limitation: By learning the mapping from problem parameters to value function approximations, the method obviates the need to explicitly construct cuts for every new instance, addressing a key limitation of traditional decomposition methods.
• Addressing $\nu$-SDDP Limitations: It resolves the constraints of $\nu$-SDDP by incorporating the history of generated cuts (via the Transformer's sequential nature) and extending applicability beyond linear programs to non-linear convex problems.
• Efficiency-Quality Trade-off: The method offers a favorable trade-off, significantly reducing computation time while preserving solution quality, particularly for large-scale instances where traditional SDDP becomes prohibitively slow.

The authors conclude that while the method relies on the quality of the training data (generated by SDDP), it successfully learns to generate subgradient cutting planes without compromising solution quality, offering a scalable alternative for complex stochastic optimization.