From Sequential to Parallel: Reformulating Dynamic Programming as GPU Kernels for Large-Scale Stochastic Combinatorial Optimization

Haohua Zhang; Jingyi Zhao; Linxin Yang; Qile He; Tian Ding

arxiv: 2602.05179 · v3 · submitted 2026-02-05 · 🧮 math.OC · cs.DC

From Sequential to Parallel: Reformulating Dynamic Programming as GPU Kernels for Large-Scale Stochastic Combinatorial Optimization

Jingyi Zhao , Linxin Yang , Haohua Zhang , Qile He , Tian Ding This is my paper

Pith reviewed 2026-05-16 07:53 UTC · model grok-4.3

classification 🧮 math.OC cs.DC

keywords stochastic programmingdynamic programmingGPU accelerationsample average approximationinteger recoursevehicle routingcombinatorial optimization

0 comments

The pith

Reformulating dynamic programming as batched GPU kernels makes structured integer recourse tractable for over a million scenarios in stochastic programming.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops GPU-based kernels that parallelize dynamic programming updates for second-stage combinatorial problems in stochastic programming, enabling exact solutions across millions of scenarios instead of relying on simplified linear models. By vectorizing Bellman updates across scenarios, layers, and action choices, the approach achieves near-linear scaling and speedups of two to five orders of magnitude. This allows evaluation of much larger scenario sets and more first-stage candidates within time limits, resulting in stronger decisions for problems like stochastic vehicle routing and inventory reinsertion. A reader would care because it opens practical paths to realistic large-scale stochastic discrete optimization that were previously computationally infeasible.

Core claim

The key innovation is a set of hardware-aware, scenario-batched GPU kernels that expose parallelism across scenarios, dynamic-programming layers, and route or action options, enabling Bellman updates to be executed in a single pass over more than 1,000,000 realizations with near-linear scaling in the number of scenarios.

What carries the argument

Scenario-batched GPU kernels for vectorized Bellman updates in dynamic programming recourses, exposing parallelism across scenarios, layers, and actions.

If this is right

Larger scenario sets become feasible in sample average approximation without prohibitive runtimes.
Many more first-stage decision candidates can be evaluated in fixed time budgets.
Consistently stronger SAA solutions are obtained for stochastic combinatorial problems.
Nearly linear scaling allows the method to handle increasing numbers of scenarios efficiently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This could extend to other DP-based combinatorial structures in stochastic settings beyond routing and inventory.
Similar parallelization strategies might apply to other sequential optimization algorithms on GPUs.
Integration with advanced sampling methods could further enhance decision quality in these large-scale problems.

Load-bearing premise

The dynamic programming structure for the recourse problem admits efficient vectorization and batched execution on GPUs with acceptable memory and synchronization costs.

What would settle it

Run the GPU kernels on a stochastic vehicle routing problem with 1,000,000 scenarios and measure if the runtime is reduced by at least two orders of magnitude compared to sequential execution while producing improved first-stage solutions.

Figures

Figures reproduced from arXiv: 2602.05179 by Haohua Zhang, Jingyi Zhao, Linxin Yang, Qile He, Tian Ding.

**Figure 1.** Figure 1: 2D DP parallelism on GPU (scenarios × predecessors). Each row corresponds to a destination state i, each block within a row represents a scenario ω, and colored bars indicate feasible predecessors p < i. For each (i, ω) pair, all predecessors are expanded in parallel to form the set {J ω (p)+A ω (p, i) : p < i}, followed by a column-wise min-reduction over p that yields J ω (i). 2D Parallelism on GPU. From… view at source ↗

**Figure 2.** Figure 2: 3D DP parallelism on GPU (scenarios × transitions × route options). Each layer corresponds to a stage t, with nodes representing end-of-day inventory levels I. Colored edges denote feasible transitions I → J under scenario-specific demands d t,ω. For each tuple (ω, I→J, r), threads evaluate the cost contribution J t i (I) +A t,ω i (I, J; r), combining routing overhead with holding and stockout penalties. A… view at source ↗

**Figure 3.** Figure 3: Empirical behavior of SAA estimators in DSIRP. Top: bias under different demand distributions. Bottom: convergence with increasing scenario size. 3.2 SCALABILITY WITH THE NUMBER OF SCENARIOS. The above results confirm that larger scenario sets are statistically necessary to reduce bias and achieve consistency in stochastic programming. We next examine whether such scaling is computationally feasible. We e… view at source ↗

**Figure 4.** Figure 4: Runtime comparisons of CPU and GPU implementations across different scaling regimes. Left: scaling behavior under 104 –106 scenarios for CVRPSD. Right: large-scale evaluation for DSIRP. driven scenario sets used in our SAA experiments, directly supporting the statistical benefits documented in the previous subsection. 3.3 IMPACT OF SEARCHING SCENARIO SET SIZE ON DECISION QUALITY We next examine how the nu… view at source ↗

**Figure 6.** Figure 6: Quality of the best solution obtained at each time under a fixed time budget. GPU consistently achieves better decisions due to faster evaluation and thus larger effective search effort. Results. When observing only few scenarios (e.g., a single scenario), the resulting first-stage solution is severely biased and performs poorly. Increasing the scale of available scenarios consistently improves robustnes… view at source ↗

**Figure 8.** Figure 8: Relationship between GPU utilization and the number of scenarios/customers in CVRPSD instances. To assess the viability of our method with respect to GPU memory requirements, we conduct dedicated experiments for both the GPU-based CVRPSD and DSIRP solvers. Figures 8 and 7 summarize the resulting GPU-memory consumption. Results for both CVRPSD and DSIRP show that GPU memory usage grows strictly linearly … view at source ↗

**Figure 9.** Figure 9: Example of splitting a giant tour into feasible routes under a given demand scenario. The extensive model is: min x, z, u, l 1 |Ω| X ω∈Ω   X k∈K X (i,j)∈A (δij + Sj ) x ω ijk + β X k∈K l ω k   (5) s.t. X k∈K X i∈N x ω ijk = 1 ∀j ∈ N \ {0}, ∀ω (6) X k∈K X j∈N x ω ijk = 1 ∀i ∈ N \ {0}, ∀ω (7) X i∈N x ω ijk = X i ′∈N x ω ji′k ∀j ∈ N \ {0}, ∀k ∈ K, ∀ω (8) X j̸=0 x ω 0jk = X i̸=0 x ω i0k ≤ 1 ∀k ∈ K, ∀ω (9) … view at source ↗

**Figure 9.** Figure 9: (i) In Scenario 1, the realized demands are [14, 15, 8, 1, 8]. The second-stage routing may then split the tour into three feasible routes: (1), (2), and (4, 3, 5). (ii) In Scenario m, the realized demands are [8, 1, 5, 7, 2] with three vehicles available. The second-stage routing may then split the tour into two feasible routes: (1) and (2, 4, 3, 5). It is well understood that searching robust first-stage… view at source ↗

read the original abstract

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) layers, and route or action options, enabling Bellman updates to be executed in a single pass over more than 1,000,000 realizations. We evaluate the approach in two representative SP settings: a vectorized split operator for stochastic vehicle routing and a DP for inventory reinsertion. Implementation scales nearly linearly in the number of scenarios and achieves a one-two to four-five orders of magnitude speedup, allowing far larger scenario sets and reliably stronger first-stage decisions. The computational leverage directly improves decision quality: much larger scenario sets and many more first-stage candidates can be evaluated within fixed time budgets, consistently yielding stronger SAA solutions. Our results show that structured integer recourse operators are tractable at scales previously considered impossible, providing a practical path to large-scale, realistic stochastic discrete optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The GPU batched DP reformulation delivers practical speedups for large-scale SAA but the cross-layer parallelism claim needs tighter validation on memory and exactness.

read the letter

The main point is that this work turns dynamic programming for integer recourse into GPU kernels that batch across scenarios, layers, and actions, letting you run a million scenarios for vehicle routing split operators and inventory reinsertion without the usual second-stage bottleneck. They report near-linear scaling and speedups from two to five orders of magnitude, which in turn lets them evaluate more first-stage candidates and get measurably better SAA solutions within the same wall time. That part is useful if it holds. The specific hardware-aware kernels for scenario-batched Bellman updates in combinatorial recourse look like the actual new piece; prior GPU DP work exists in other fields, but the adaptation to stochastic programming with NP-hard recourse and the empirical link to improved decision quality are the concrete advances here. The timing results and decision-quality gains are presented clearly enough to take seriously for the two test cases. The soft spot is the handling of sequential layer dependencies. The abstract claims single-pass updates with parallelism across layers, yet standard DP requires layer k to finish before k+1. If they unroll or vectorize without extra synchronization or memory blowup, the reported gains could be limited to shallow DPs or come at the cost of numerical stability. The paper should show memory footprints, error checks against sequential baselines, and scaling curves for deeper recursions to close this. This is for operations research people who already work with scenario-based stochastic programs and have GPU access. A reader trying to scale integer recourse would find the approach worth testing, especially if code is released. It deserves peer review because the core reformulation is testable and the performance claims are specific enough for referees to check.

Referee Report

2 major / 1 minor

Summary. The paper develops a GPU-based framework that reformulates dynamic programming recursions for structured integer recourse problems as scenario-batched kernels, exposing parallelism across scenarios, DP layers, and action options to enable single-pass Bellman updates for over 1,000,000 realizations. It demonstrates the approach on a vectorized split operator for stochastic vehicle routing and an inventory reinsertion DP, reporting near-linear scaling in scenarios and speedups of 10^2 to 10^5 relative to sequential baselines, which in turn allows larger scenario sets and stronger first-stage SAA decisions.

Significance. If the correctness and scaling claims hold, the work would make exact second-stage combinatorial recourse tractable at scales previously limited to linear or approximate models, directly improving decision quality in realistic stochastic discrete optimization via larger scenario sets and more first-stage candidates within fixed compute budgets.

major comments (2)

[Abstract] Abstract and kernel design section: the claim that Bellman updates execute 'in a single pass' over DP layers while exposing cross-layer parallelism requires explicit description of how sequential dependencies (value at layer k depends on layer k-1) are preserved without either exploding memory via full unrolling or introducing unquantified synchronization barriers; the reported linear scaling and 10^4-10^5 speedups may not generalize if this is only feasible for shallow layers.
[Empirical evaluation] Empirical evaluation section: the central performance and decision-quality claims rest on limited benchmark detail (no error analysis, full implementation pseudocode, or per-layer timing breakdowns), so it is unclear whether the observed speedups preserve exact DP optimality or arise from approximations that could degrade SAA solution quality for deeper recursions.

minor comments (1)

Clarify notation for the 'vectorized split operator' and 'inventory DP' to ensure readers can reproduce the kernel mapping from standard Bellman recursion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful comments, which have helped us improve the clarity and completeness of the manuscript. We address each major comment below and have made revisions to the paper as indicated.

read point-by-point responses

Referee: [Abstract] Abstract and kernel design section: the claim that Bellman updates execute 'in a single pass' over DP layers while exposing cross-layer parallelism requires explicit description of how sequential dependencies (value at layer k depends on layer k-1) are preserved without either exploding memory via full unrolling or introducing unquantified synchronization barriers; the reported linear scaling and 10^4-10^5 speedups may not generalize if this is only feasible for shallow layers.

Authors: We agree that additional detail is needed on this point. In the revised manuscript, we have expanded the kernel design section to explicitly describe our approach: DP layers are processed sequentially to respect dependencies, but within each layer we parallelize across all scenarios and action options using batched GPU kernels. Sequential dependencies are handled via a double-buffering technique that maintains only the previous layer's value function in memory, avoiding full unrolling. Synchronization barriers are implemented using CUDA block-level __syncthreads() and inter-layer stream synchronization, with their overhead explicitly measured and reported in the new per-layer timing analysis. This design enables the observed scaling even for deeper recursions, as validated in our experiments with up to 20 layers. We have also added a pseudocode listing and a dataflow diagram. revision: yes
Referee: [Empirical evaluation] Empirical evaluation section: the central performance and decision-quality claims rest on limited benchmark detail (no error analysis, full implementation pseudocode, or per-layer timing breakdowns), so it is unclear whether the observed speedups preserve exact DP optimality or arise from approximations that could degrade SAA solution quality for deeper recursions.

Authors: We thank the referee for highlighting this. The GPU kernels implement the exact same Bellman recursion as the sequential version, with no approximations; any differences are only due to floating-point arithmetic. In the revised version, we have added: (1) an error analysis comparing GPU and CPU outputs on small instances, showing exact agreement within 1e-6 relative error; (2) full implementation pseudocode in the appendix; (3) per-layer timing breakdowns demonstrating that the speedups come from parallelism rather than reduced computation. These additions confirm that optimality is preserved and SAA solution quality is not degraded. We have also included results for deeper DP instances to address generalizability. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic reformulation and empirical scaling results are self-contained

full rationale

The paper describes a direct GPU kernel reformulation of standard DP recursion for scenario-batched Bellman updates, with claims resting on implementation details and measured speedups rather than any derivation that reduces to fitted parameters, self-citations, or imported uniqueness theorems. No equations are presented that equate a prediction to its own inputs by construction, and the parallelism across layers is framed as an engineering choice whose correctness is validated by timing experiments, not by circular reference to prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on standard dynamic programming correctness and GPU parallel execution assumptions; no new free parameters or invented entities are introduced.

axioms (1)

standard math Dynamic programming correctly computes the optimal second-stage value for each scenario
Invoked implicitly when claiming that the GPU kernels solve the exact recourse problems.

pith-pipeline@v0.9.0 · 5548 in / 1049 out tokens · 24735 ms · 2026-05-16T07:53:04.279051+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Neuro-dynamic programming: an overview

Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. InPro- ceedings of 1995 34th IEEE conference on decision and control, volume 1, pp. 560–564. IEEE,

work page 1995
[2]

APACrefauthors \ 1959

doi: 10.1007/BF01386390. 10 Published as a conference paper at ICLR 2026 Joseph Farrington, Kezhi Li, Wai Keong Wong, and Martin Utley. Going faster to see further: Gpu-accelerated value iteration and simulation for perishable inventory control using jax.arXiv preprint arXiv:2303.10672,

work page doi:10.1007/bf01386390 2026
[3]

A dynamic programming al- gorithm for solving the k-color shortest path problem.Optimization Letters, 15(6):1973–1992,

Daniele Ferone, Paola Festa, Serena Fugaro, and Tommaso Pastore. A dynamic programming al- gorithm for solving the k-color shortest path problem.Optimization Letters, 15(6):1973–1992,

work page 1973
[4]

A gpu-accelerated interior point method for radiation therapy optimization.arXiv preprint arXiv:2405.03584,

Felix Liu, Albin Fredriksson, and Stefano Markidis. A gpu-accelerated interior point method for radiation therapy optimization.arXiv preprint arXiv:2405.03584,

work page arXiv
[5]

Haihao Lu and Jinwen Yang. cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia.arXiv preprint arXiv:2311.12180,

work page arXiv
[6]

A simple and effective evolutionary algorithm for the vehicle routing problem

Christian Prins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & operations research, 31(12):1985–2002,

work page 1985
[7]

GPU acceleration of ADMM for large-scale quadratic programming,

ISSN 0743-7315. doi: 10.1016/j.jpdc.2020.05.021. URLhttp://dx.doi.org/10. 1016/j.jpdc.2020.05.021. Alexander Shapiro. Monte carlo sampling methods.Handbooks in operations research and man- agement science, 10:353–425,

work page doi:10.1016/j.jpdc.2020.05.021 2020
[8]

Dynamic programming algorithms for the integer programming problem—i: The integer programming problem viewed as a knapsack type problem.Operations Research, 16(1): 103–121,

11 Published as a conference paper at ICLR 2026 Jeremy F Shapiro. Dynamic programming algorithms for the integer programming problem—i: The integer programming problem viewed as a knapsack type problem.Operations Research, 16(1): 103–121,

work page 2026
[9]

Large neighborhood and hybrid genetic search for inventory routing problems.arXiv preprint arXiv:2506.03172,

Jingyi Zhao, Claudia Archetti, Tuan Anh Pham, and Thibaut Vidal. Large neighborhood and hybrid genetic search for inventory routing problems.arXiv preprint arXiv:2506.03172,

work page arXiv
[10]

A APPENDIX A.1 RELATEDWORKS DP has long been a foundation of combinatorial optimization and stochastic control Carraway et al. (1989); Chu (2011); Paschos (2014), underpinning exact algorithms for the traveling salesman prob- lem Bellman (1962); Malandraki & Dial (1996), knapsack variants Bertsimas & Demir (2002), and shortest-path computations Ferone et ...

work page 1989
[11]

Thus, the updated cost-to-go vector at staget+ 1is: J ω t+1 = 2 3 . This computation reflects a forward shortest-path propagation over a layered graph, where the cost of reaching each state in the next stage is determined by minimizing over all incoming transitions from the previous stage. Algorithm 1High-level Scenario-Batched GPU Forward DP Input:Scenar...

work page 2026
[12]

The extensive model is: min x, z, u, l 1 |Ω| X ω∈Ω  X k∈K X (i,j)∈A (δij +S j)x ω ijk +β X k∈K lω k   (5) s.t

Second stage Scenario 1 Scenario 2 Scenario m⋯ ⋯ 1 2 4 3 5 1 2 4 3 5 Figure 9:Example of splitting a giant tour into feasible routes under a given demand scenario. The extensive model is: min x, z, u, l 1 |Ω| X ω∈Ω  X k∈K X (i,j)∈A (δij +S j)x ω ijk +β X k∈K lω k   (5) s.t. X k∈K X i∈N xω ijk = 1∀j∈ N \ {0},∀ω(6) X k∈K X j∈N xω ijk = 1∀i∈ N \ {0},∀ω(7...

work page 2026
[13]

The second-stage routing may then split the tour into three feasible routes:(1),(2), and(4,3,5)

(i) In Scenario 1, the realized demands are[14,15,8,1,8]. The second-stage routing may then split the tour into three feasible routes:(1),(2), and(4,3,5). (ii) In Scenariom, the realized demands are[8,1,5,7,2]with three vehicles available. The second-stage routing may then split the tour into two feasible routes:(1)and(2,4,3,5). It is well understood that...

work page 2003
[14]

We construct a transition cost matrixA ω ∈R 3×3 where the(p, i)entry represents the cost of serving customersσ p+1 toσ i in one route, if the cumulative demand is within capacity

Letf ω(i)denote the minimum cost to serve customersσ 1 throughσ i. We construct a transition cost matrixA ω ∈R 3×3 where the(p, i)entry represents the cost of serving customersσ p+1 toσ i in one route, if the cumulative demand is within capacity. 15 Published as a conference paper at ICLR 2026 Algorithm 2GPU Splitting Algorithm Input:Scenariosω∈Ω Input:Gl...

work page 2026
[15]

no delivery

Thus, the masked transition matrix becomes: Aω =   x4 4 +∞ x x4 +∞ x x x4 x x x x   , the forward DP proceedscolumn by columnfrom the initializationJ ω(0) = 0: J ω(1) =J ω(0) +A ω(0,1) = 0 + 4 = 4 16 Published as a conference paper at ICLR 2026 (since only the predecessorp= 0is admissible whenj= 1). Then J ω(2) = min J ω(1) +A ω(1,2), J ω(0) +A ω(0,...

work page 2026
[16]

18 Published as a conference paper at ICLR 2026 Policy insight.- Day 1: fromI= 1, deliveringq= 1(replenish to full) is optimal, leading toJ= 1 with cost1 + 1 =

work page 2026
[17]

A.5 MONTECARLOMETHODPROPOSITION

(ii) In general, if evaluatingA(I, J)requires enumerating multiple route options r∈ K, thenA(I, J) = min r A(I, J;r), and GPU parallelism naturally extends to three dimensions (ω, I→J, r)with reductions first overrand then overI. A.5 MONTECARLOMETHODPROPOSITION. Empirical Risk Minimization(ERM) method is analogous to the Monte Carlo method for estimating ...

work page arXiv 2003
[18]

The exper- 20 Published as a conference paper at ICLR 2026 Table 4: Relationship between explored candidates and objective improvement in the CVRPSD dataset

and observe the same behavior as in DSIRP: as the time budget increases and more first-stage candidates are explored, the framework consistently returns equal or better solutions, with no degradation in solution quality. The exper- 20 Published as a conference paper at ICLR 2026 Table 4: Relationship between explored candidates and objective improvement i...

work page 2026

[1] [1]

Neuro-dynamic programming: an overview

Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. InPro- ceedings of 1995 34th IEEE conference on decision and control, volume 1, pp. 560–564. IEEE,

work page 1995

[2] [2]

APACrefauthors \ 1959

doi: 10.1007/BF01386390. 10 Published as a conference paper at ICLR 2026 Joseph Farrington, Kezhi Li, Wai Keong Wong, and Martin Utley. Going faster to see further: Gpu-accelerated value iteration and simulation for perishable inventory control using jax.arXiv preprint arXiv:2303.10672,

work page doi:10.1007/bf01386390 2026

[3] [3]

A dynamic programming al- gorithm for solving the k-color shortest path problem.Optimization Letters, 15(6):1973–1992,

Daniele Ferone, Paola Festa, Serena Fugaro, and Tommaso Pastore. A dynamic programming al- gorithm for solving the k-color shortest path problem.Optimization Letters, 15(6):1973–1992,

work page 1973

[4] [4]

A gpu-accelerated interior point method for radiation therapy optimization.arXiv preprint arXiv:2405.03584,

Felix Liu, Albin Fredriksson, and Stefano Markidis. A gpu-accelerated interior point method for radiation therapy optimization.arXiv preprint arXiv:2405.03584,

work page arXiv

[5] [5]

Haihao Lu and Jinwen Yang. cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia.arXiv preprint arXiv:2311.12180,

work page arXiv

[6] [6]

A simple and effective evolutionary algorithm for the vehicle routing problem

Christian Prins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & operations research, 31(12):1985–2002,

work page 1985

[7] [7]

GPU acceleration of ADMM for large-scale quadratic programming,

ISSN 0743-7315. doi: 10.1016/j.jpdc.2020.05.021. URLhttp://dx.doi.org/10. 1016/j.jpdc.2020.05.021. Alexander Shapiro. Monte carlo sampling methods.Handbooks in operations research and man- agement science, 10:353–425,

work page doi:10.1016/j.jpdc.2020.05.021 2020

[8] [8]

Dynamic programming algorithms for the integer programming problem—i: The integer programming problem viewed as a knapsack type problem.Operations Research, 16(1): 103–121,

11 Published as a conference paper at ICLR 2026 Jeremy F Shapiro. Dynamic programming algorithms for the integer programming problem—i: The integer programming problem viewed as a knapsack type problem.Operations Research, 16(1): 103–121,

work page 2026

[9] [9]

Large neighborhood and hybrid genetic search for inventory routing problems.arXiv preprint arXiv:2506.03172,

Jingyi Zhao, Claudia Archetti, Tuan Anh Pham, and Thibaut Vidal. Large neighborhood and hybrid genetic search for inventory routing problems.arXiv preprint arXiv:2506.03172,

work page arXiv

[10] [10]

A APPENDIX A.1 RELATEDWORKS DP has long been a foundation of combinatorial optimization and stochastic control Carraway et al. (1989); Chu (2011); Paschos (2014), underpinning exact algorithms for the traveling salesman prob- lem Bellman (1962); Malandraki & Dial (1996), knapsack variants Bertsimas & Demir (2002), and shortest-path computations Ferone et ...

work page 1989

[11] [11]

Thus, the updated cost-to-go vector at staget+ 1is: J ω t+1 = 2 3 . This computation reflects a forward shortest-path propagation over a layered graph, where the cost of reaching each state in the next stage is determined by minimizing over all incoming transitions from the previous stage. Algorithm 1High-level Scenario-Batched GPU Forward DP Input:Scenar...

work page 2026

[12] [12]

The extensive model is: min x, z, u, l 1 |Ω| X ω∈Ω  X k∈K X (i,j)∈A (δij +S j)x ω ijk +β X k∈K lω k   (5) s.t

Second stage Scenario 1 Scenario 2 Scenario m⋯ ⋯ 1 2 4 3 5 1 2 4 3 5 Figure 9:Example of splitting a giant tour into feasible routes under a given demand scenario. The extensive model is: min x, z, u, l 1 |Ω| X ω∈Ω  X k∈K X (i,j)∈A (δij +S j)x ω ijk +β X k∈K lω k   (5) s.t. X k∈K X i∈N xω ijk = 1∀j∈ N \ {0},∀ω(6) X k∈K X j∈N xω ijk = 1∀i∈ N \ {0},∀ω(7...

work page 2026

[13] [13]

The second-stage routing may then split the tour into three feasible routes:(1),(2), and(4,3,5)

(i) In Scenario 1, the realized demands are[14,15,8,1,8]. The second-stage routing may then split the tour into three feasible routes:(1),(2), and(4,3,5). (ii) In Scenariom, the realized demands are[8,1,5,7,2]with three vehicles available. The second-stage routing may then split the tour into two feasible routes:(1)and(2,4,3,5). It is well understood that...

work page 2003

[14] [14]

We construct a transition cost matrixA ω ∈R 3×3 where the(p, i)entry represents the cost of serving customersσ p+1 toσ i in one route, if the cumulative demand is within capacity

Letf ω(i)denote the minimum cost to serve customersσ 1 throughσ i. We construct a transition cost matrixA ω ∈R 3×3 where the(p, i)entry represents the cost of serving customersσ p+1 toσ i in one route, if the cumulative demand is within capacity. 15 Published as a conference paper at ICLR 2026 Algorithm 2GPU Splitting Algorithm Input:Scenariosω∈Ω Input:Gl...

work page 2026

[15] [15]

no delivery

Thus, the masked transition matrix becomes: Aω =   x4 4 +∞ x x4 +∞ x x x4 x x x x   , the forward DP proceedscolumn by columnfrom the initializationJ ω(0) = 0: J ω(1) =J ω(0) +A ω(0,1) = 0 + 4 = 4 16 Published as a conference paper at ICLR 2026 (since only the predecessorp= 0is admissible whenj= 1). Then J ω(2) = min J ω(1) +A ω(1,2), J ω(0) +A ω(0,...

work page 2026

[16] [16]

18 Published as a conference paper at ICLR 2026 Policy insight.- Day 1: fromI= 1, deliveringq= 1(replenish to full) is optimal, leading toJ= 1 with cost1 + 1 =

work page 2026

[17] [17]

A.5 MONTECARLOMETHODPROPOSITION

(ii) In general, if evaluatingA(I, J)requires enumerating multiple route options r∈ K, thenA(I, J) = min r A(I, J;r), and GPU parallelism naturally extends to three dimensions (ω, I→J, r)with reductions first overrand then overI. A.5 MONTECARLOMETHODPROPOSITION. Empirical Risk Minimization(ERM) method is analogous to the Monte Carlo method for estimating ...

work page arXiv 2003

[18] [18]

The exper- 20 Published as a conference paper at ICLR 2026 Table 4: Relationship between explored candidates and objective improvement in the CVRPSD dataset

and observe the same behavior as in DSIRP: as the time budget increases and more first-stage candidates are explored, the framework consistently returns equal or better solutions, with no degradation in solution quality. The exper- 20 Published as a conference paper at ICLR 2026 Table 4: Relationship between explored candidates and objective improvement i...

work page 2026