Id: arxiv/2602.05179 Url: https://arxiv.org/abs/2602.05179 Tags: math.OC, cs.DC Score: 0 Title: From Sequential to Parallel: Reformulating Dynamic Programming as GPU Kernels for Large-Scale Stochastic Combinatorial Optimization Domain: math.OC Source: arxiv Authors: Jingyi Zhao, Linxin Yang, Haohua Zhang, Qile He, Tian Ding Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-05 Page: https://delphi.science/r/arxiv/2602.05179 A major bottleneck in scenario-based Sample Average Approximation (SAA) for stochastic programming (SP) is the cost of solving an exact second-stage problem for every scenario, especially when each scenario contains an NP-hard combinatorial structure. This has led much of the SP literature to restrict the second stage to linear or simplified models. We develop a GPU-based framework that makes structured integer recourse operators tractable at scale. The key innovation is a set of hardware-aware, scenario-batched GPU kernels that expose parallelism across scenarios, dynamic-programming (DP)…