{"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","summary":"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)…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-05","reactions":{}}