Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization

• URL: http://arxiv.org/abs/2404.02583v1
• Date: Wed, 3 Apr 2024 09:08:15 GMT
• Title: Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization
• Authors: Chanyeong Kim, Jongwoong Park, Hyunglip Bae, Woo Chang Kim,
• Abstract summary: We introduce TranSDDP, a novel Transformer-based stagewise decomposition algorithm. We show it efficiently generates a piecewise linear approximation for the value function.
• Score: 1.3124513975412255
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• M-HOF-Opt: Multi-Objective Hierarchical Output Feedback Optimization via Multiplier Induced Loss Landscape Scheduling [4.499391876093543]
  We address the online choice of weight multipliers for multi-objective optimization of many loss terms parameterized by neural works. Our method is multiplier-free and operates at the timescale of epochs. It also circumvents the excessive memory requirements and heavy computational burden of existing multi-objective deep learning methods.
  arXiv  Detail & Related papers  (2024-03-20T16:38:26Z)
• Toward TransfORmers: Revolutionizing the Solution of Mixed Integer Programs with Transformers [3.107843027522116]
  We introduce an innovative deep learning framework that employs a transformer model to address the challenges of mixed-integer programs. Our approach is the first to utilize transformers to predict the binary variables of a mixed-integer programming (MIP) problem. We present an efficient algorithm in which CLSP solutions are learned through a transformer neural network.
  arXiv  Detail & Related papers  (2024-02-20T21:13:38Z)
• Non-stationary Reinforcement Learning under General Function Approximation [60.430936031067006]
  We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA. We show that SW-OPEA is provably efficient as long as the variation budget is not significantly large.
  arXiv  Detail & Related papers  (2023-06-01T16:19:37Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Complexity of Stochastic Dual Dynamic Programming [7.177693955272473]
  We first establish the number of iteration, i.e., complexity, required by a basic dynamic cutting plane method for solving simple multi-stage optimization problems. We then refine these basic tools and establish the iteration complexity for both deterministic and dual dynamic programming methods.
  arXiv  Detail & Related papers  (2019-12-16T20:56:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.