Newsvendor
This tutorial was generated using Literate.jl. Download the source as a .jl file. Download the source as a .ipynb file.
This example is based on the classical newsvendor problem, but features an AR(1) spot-price.
V(x[t-1], ω[t]) = max p[t] × u[t]
subject to x[t] = x[t-1] - u[t] + ω[t]
u[t] ∈ [0, 1]
x[t] ≥ 0
p[t] = p[t-1] + ϕ[t]The initial conditions are
x[0] = 2.0
p[0] = 1.5
ω[t] ~ {0, 0.05, 0.10, ..., 0.45, 0.5} with uniform probability.
ϕ[t] ~ {-0.25, -0.125, 0.125, 0.25} with uniform probability.using SDDP, HiGHS, Statistics, Testfunction joint_distribution(; kwargs...) names = tuple([first(kw) for kw in kwargs]...) values = tuple([last(kw) for kw in kwargs]...) output_type = NamedTuple{names,Tuple{eltype.(values)...}} distribution = map(output_type, Base.product(values...)) return distribution[:]endfunction newsvendor_example(; cut_type) model = SDDP.PolicyGraph( SDDP.LinearGraph(3); sense = :Max, upper_bound = 50.0, optimizer = HiGHS.Optimizer, ) do subproblem, stage @variables(subproblem, begin x >= 0, (SDDP.State, initial_value = 2) 0 <= u <= 1 w end) @constraint(subproblem, x.out == x.in - u + w) SDDP.add_objective_state( subproblem; initial_value = 1.5, lower_bound = 0.75, upper_bound = 2.25, lipschitz = 100.0, ) do y, ω return y + ω.price_noise end noise_terms = joint_distribution(; demand = 0:0.05:0.5, price_noise = [-0.25, -0.125, 0.125, 0.25], ) SDDP.parameterize(subproblem, noise_terms) do ω fix(w, ω.demand) price = SDDP.objective_state(subproblem) @stageobjective(subproblem, price * u) end end SDDP.train( model; log_frequency = 10, time_limit = 20.0, cut_type = cut_type, ) @test SDDP.calculate_bound(model) ≈ 4.04 atol = 0.05 results = SDDP.simulate(model, 500) objectives = [sum(s[:stage_objective] for s in simulation) for simulation in results] @test round(Statistics.mean(objectives); digits = 2) ≈ 4.04 atol = 0.1 returnendnewsvendor_example(; cut_type = SDDP.SINGLE_CUT)newsvendor_example(; cut_type = SDDP.MULTI_CUT)-------------------------------------------------------------------
SDDP.jl (c) Oscar Dowson and contributors, 2017-26
-------------------------------------------------------------------
problem
nodes : 3
state variables : 1
scenarios : 8.51840e+04
existing cuts : false
options
solver : serial mode
risk measure : SDDP.Expectation()
sampling scheme : SDDP.InSampleMonteCarlo
subproblem structure
VariableRef : [6, 6]
AffExpr in MOI.EqualTo{Float64} : [1, 3]
AffExpr in MOI.LessThan{Float64} : [2, 2]
VariableRef in MOI.GreaterThan{Float64} : [3, 4]
VariableRef in MOI.LessThan{Float64} : [3, 3]
numerical stability report
matrix range [8e-01, 2e+00]
objective range [1e+00, 2e+00]
bounds range [1e+00, 1e+02]
rhs range [5e+01, 5e+01]
-------------------------------------------------------------------
iteration simulation bound time (s) solves pid
-------------------------------------------------------------------
10 5.500000e+00 5.473308e+00 1.185789e-01 1350 1
20 4.062500e+00 4.451907e+00 1.598170e-01 2700 1
30 2.993750e+00 4.101372e+00 2.079499e-01 4050 1
40 5.750000e+00 4.095757e+00 2.578881e-01 5400 1
50 5.125000e+00 4.093536e+00 3.092740e-01 6750 1
60 3.737500e+00 4.089225e+00 3.630240e-01 8100 1
70 4.500000e+00 4.088152e+00 4.167879e-01 9450 1
80 4.950000e+00 4.087904e+00 4.734530e-01 10800 1
90 4.125000e+00 4.087756e+00 5.318689e-01 12150 1
100 3.275000e+00 4.086300e+00 6.292870e-01 13500 1
110 5.250000e+00 4.086125e+00 6.949730e-01 14850 1
120 4.975000e+00 4.086054e+00 7.726009e-01 16200 1
130 3.500000e+00 4.085422e+00 8.416719e-01 17550 1
140 4.593750e+00 4.085327e+00 9.092081e-01 18900 1
150 3.000000e+00 4.085258e+00 9.801769e-01 20250 1
160 2.700000e+00 4.085247e+00 1.053560e+00 21600 1
170 3.812500e+00 4.085151e+00 1.125241e+00 22950 1
180 3.875000e+00 4.085121e+00 1.199090e+00 24300 1
190 4.737500e+00 4.085102e+00 1.271154e+00 25650 1
200 2.906250e+00 4.085073e+00 1.343337e+00 27000 1
210 3.750000e+00 4.085050e+00 1.418545e+00 28350 1
220 5.050000e+00 4.085037e+00 1.493215e+00 29700 1
230 2.925000e+00 4.085012e+00 1.564452e+00 31050 1
240 4.500000e+00 4.084970e+00 1.649350e+00 32400 1
250 4.875000e+00 4.084908e+00 1.730031e+00 33750 1
260 3.675000e+00 4.084905e+00 1.831241e+00 35100 1
270 4.725000e+00 4.084903e+00 1.913845e+00 36450 1
280 3.437500e+00 4.084900e+00 1.990686e+00 37800 1
290 3.750000e+00 4.084879e+00 2.070795e+00 39150 1
300 4.125000e+00 4.084879e+00 2.152268e+00 40500 1
310 4.875000e+00 4.084803e+00 2.231678e+00 41850 1
320 5.625000e+00 4.084803e+00 2.308679e+00 43200 1
330 3.825000e+00 4.084800e+00 2.389031e+00 44550 1
340 3.300000e+00 4.084796e+00 2.499091e+00 45900 1
350 5.887500e+00 4.084796e+00 2.581101e+00 47250 1
360 3.600000e+00 4.084786e+00 2.661508e+00 48600 1
370 3.618750e+00 4.084786e+00 2.740718e+00 49950 1
380 4.968750e+00 4.084782e+00 2.818945e+00 51300 1
390 3.300000e+00 4.084780e+00 2.897484e+00 52650 1
400 4.006250e+00 4.084779e+00 2.983754e+00 54000 1
410 4.050000e+00 4.084779e+00 3.069248e+00 55350 1
420 5.125000e+00 4.084776e+00 3.152664e+00 56700 1
430 4.000000e+00 4.084776e+00 3.234980e+00 58050 1
440 4.125000e+00 4.084776e+00 3.320356e+00 59400 1
450 3.112500e+00 4.084776e+00 3.406728e+00 60750 1
460 3.750000e+00 4.084771e+00 3.492590e+00 62100 1
470 3.187500e+00 4.084767e+00 3.570855e+00 63450 1
480 3.031250e+00 4.084757e+00 3.660373e+00 64800 1
490 4.181250e+00 4.084753e+00 3.745300e+00 66150 1
500 3.187500e+00 4.084746e+00 3.835334e+00 67500 1
510 4.875000e+00 4.084741e+00 3.920603e+00 68850 1
520 3.900000e+00 4.084737e+00 4.004443e+00 70200 1
530 4.350000e+00 4.084737e+00 4.089284e+00 71550 1
540 4.212500e+00 4.084737e+00 4.174922e+00 72900 1
550 4.250000e+00 4.084734e+00 4.263178e+00 74250 1
560 3.750000e+00 4.084734e+00 4.349487e+00 75600 1
570 5.306250e+00 4.084730e+00 4.436294e+00 76950 1
580 4.725000e+00 4.084730e+00 4.521765e+00 78300 1
590 4.250000e+00 4.084730e+00 4.629561e+00 79650 1
600 4.000000e+00 4.084730e+00 4.719140e+00 81000 1
610 4.600000e+00 4.084730e+00 4.803530e+00 82350 1
620 3.375000e+00 4.084730e+00 4.890443e+00 83700 1
630 3.981250e+00 4.084725e+00 4.981355e+00 85050 1
640 3.250000e+00 4.084725e+00 5.070758e+00 86400 1
650 3.625000e+00 4.084725e+00 5.156722e+00 87750 1
660 4.781250e+00 4.084725e+00 5.246319e+00 89100 1
670 4.275000e+00 4.084725e+00 5.345293e+00 90450 1
680 2.731250e+00 4.084725e+00 5.446107e+00 91800 1
690 5.237500e+00 4.084725e+00 5.546939e+00 93150 1
700 3.325000e+00 4.084725e+00 5.640540e+00 94500 1
710 4.750000e+00 4.084725e+00 5.744030e+00 95850 1
720 4.537500e+00 4.084725e+00 5.845048e+00 97200 1
730 4.725000e+00 4.084725e+00 5.948010e+00 98550 1
740 4.475000e+00 4.084725e+00 6.044905e+00 99900 1
750 2.893750e+00 4.084725e+00 6.142100e+00 101250 1
760 3.525000e+00 4.084725e+00 6.243254e+00 102600 1
770 3.525000e+00 4.084725e+00 6.342951e+00 103950 1
780 3.262500e+00 4.084725e+00 6.444653e+00 105300 1
790 4.918750e+00 4.084725e+00 6.546640e+00 106650 1
800 3.750000e+00 4.084725e+00 6.647260e+00 108000 1
810 4.687500e+00 4.084725e+00 6.749313e+00 109350 1
820 4.018750e+00 4.084725e+00 6.854751e+00 110700 1
830 4.725000e+00 4.084725e+00 6.957845e+00 112050 1
840 4.268750e+00 4.084725e+00 7.086730e+00 113400 1
850 5.175000e+00 4.084725e+00 7.184217e+00 114750 1
860 3.125000e+00 4.084725e+00 7.289202e+00 116100 1
870 2.762500e+00 4.084725e+00 7.384135e+00 117450 1
880 3.375000e+00 4.084725e+00 7.478942e+00 118800 1
890 3.875000e+00 4.084725e+00 7.579592e+00 120150 1
900 3.093750e+00 4.084725e+00 7.677898e+00 121500 1
910 4.125000e+00 4.084724e+00 7.786829e+00 122850 1
920 4.750000e+00 4.084724e+00 7.890593e+00 124200 1
930 5.431250e+00 4.084724e+00 7.993905e+00 125550 1
940 3.000000e+00 4.084724e+00 8.099702e+00 126900 1
950 4.243750e+00 4.084724e+00 8.201731e+00 128250 1
960 3.756250e+00 4.084724e+00 8.304923e+00 129600 1
970 3.750000e+00 4.084724e+00 8.413977e+00 130950 1
980 4.350000e+00 4.084724e+00 8.518460e+00 132300 1
990 3.375000e+00 4.084722e+00 8.622036e+00 133650 1
1000 4.750000e+00 4.084722e+00 8.723168e+00 135000 1
1010 3.825000e+00 4.084722e+00 8.825970e+00 136350 1
1020 4.000000e+00 4.084722e+00 8.921025e+00 137700 1
1030 4.500000e+00 4.084722e+00 9.027077e+00 139050 1
1040 3.637500e+00 4.084722e+00 9.135017e+00 140400 1
1050 4.050000e+00 4.084722e+00 9.236659e+00 141750 1
1060 4.925000e+00 4.084722e+00 9.341518e+00 143100 1
1070 4.500000e+00 4.084722e+00 9.451096e+00 144450 1
1080 5.000000e+00 4.084722e+00 9.560703e+00 145800 1
1090 4.393750e+00 4.084722e+00 9.664637e+00 147150 1
1100 3.750000e+00 4.084722e+00 9.775699e+00 148500 1
1110 4.306250e+00 4.084722e+00 9.900478e+00 149850 1
1120 4.200000e+00 4.084722e+00 1.001006e+01 151200 1
1130 4.343750e+00 4.084722e+00 1.012376e+01 152550 1
1140 4.650000e+00 4.084722e+00 1.023460e+01 153900 1
1150 4.537500e+00 4.084722e+00 1.034807e+01 155250 1
1160 4.250000e+00 4.084722e+00 1.046168e+01 156600 1
1170 3.312500e+00 4.084722e+00 1.057271e+01 157950 1
1180 4.968750e+00 4.084722e+00 1.068114e+01 159300 1
1190 4.062500e+00 4.084718e+00 1.079338e+01 160650 1
1200 3.750000e+00 4.084718e+00 1.090425e+01 162000 1
1210 4.387500e+00 4.084718e+00 1.101270e+01 163350 1
1220 5.237500e+00 4.084718e+00 1.113088e+01 164700 1
1230 2.737500e+00 4.084718e+00 1.123760e+01 166050 1
1240 4.587500e+00 4.084713e+00 1.134895e+01 167400 1
1250 3.750000e+00 4.084713e+00 1.145811e+01 168750 1
1260 4.250000e+00 4.084713e+00 1.157075e+01 170100 1
1270 4.125000e+00 4.084713e+00 1.167807e+01 171450 1
1280 4.125000e+00 4.084713e+00 1.178967e+01 172800 1
1290 4.250000e+00 4.084713e+00 1.190266e+01 174150 1
1300 3.350000e+00 4.084713e+00 1.201330e+01 175500 1
1310 4.187500e+00 4.084713e+00 1.212663e+01 176850 1
1320 3.437500e+00 4.084713e+00 1.224301e+01 178200 1
1330 3.731250e+00 4.084713e+00 1.235405e+01 179550 1
1340 5.250000e+00 4.084713e+00 1.247121e+01 180900 1
1350 4.750000e+00 4.084713e+00 1.258538e+01 182250 1
1360 4.725000e+00 4.084713e+00 1.270688e+01 183600 1
1370 4.150000e+00 4.084713e+00 1.282177e+01 184950 1
1380 3.287500e+00 4.084713e+00 1.296304e+01 186300 1
1390 4.875000e+00 4.084713e+00 1.307801e+01 187650 1
1400 3.075000e+00 4.084713e+00 1.318730e+01 189000 1
1410 3.875000e+00 4.084713e+00 1.329686e+01 190350 1
1420 5.662500e+00 4.084713e+00 1.341400e+01 191700 1
1430 3.550000e+00 4.084713e+00 1.352042e+01 193050 1
1440 4.687500e+00 4.084713e+00 1.363276e+01 194400 1
1450 3.243750e+00 4.084713e+00 1.374098e+01 195750 1
1460 3.250000e+00 4.084713e+00 1.385200e+01 197100 1
1470 3.250000e+00 4.084713e+00 1.396714e+01 198450 1
1480 4.075000e+00 4.084713e+00 1.408219e+01 199800 1
1490 3.200000e+00 4.084713e+00 1.420024e+01 201150 1
1500 3.406250e+00 4.084713e+00 1.431811e+01 202500 1
1510 4.593750e+00 4.084713e+00 1.443646e+01 203850 1
1520 3.750000e+00 4.084713e+00 1.455755e+01 205200 1
1530 4.637500e+00 4.084713e+00 1.466929e+01 206550 1
1540 4.125000e+00 4.084713e+00 1.478735e+01 207900 1
1550 4.875000e+00 4.084713e+00 1.490678e+01 209250 1
1560 3.437500e+00 4.084713e+00 1.502218e+01 210600 1
1570 4.293750e+00 4.084713e+00 1.513886e+01 211950 1
1580 4.500000e+00 4.084713e+00 1.525544e+01 213300 1
1590 4.350000e+00 4.084713e+00 1.537689e+01 214650 1
1600 4.575000e+00 4.084713e+00 1.549083e+01 216000 1
1610 3.175000e+00 4.084713e+00 1.561014e+01 217350 1
1620 2.625000e+00 4.084713e+00 1.573136e+01 218700 1
1630 4.750000e+00 4.084713e+00 1.585160e+01 220050 1
1640 3.625000e+00 4.084713e+00 1.597887e+01 221400 1
1650 4.375000e+00 4.084713e+00 1.612537e+01 222750 1
1660 3.700000e+00 4.084713e+00 1.623509e+01 224100 1
1670 3.625000e+00 4.084713e+00 1.635282e+01 225450 1
1680 3.750000e+00 4.084713e+00 1.646756e+01 226800 1
1690 3.700000e+00 4.084713e+00 1.658328e+01 228150 1
1700 4.125000e+00 4.084713e+00 1.670291e+01 229500 1
1710 5.093750e+00 4.084713e+00 1.681396e+01 230850 1
1720 4.500000e+00 4.084713e+00 1.692805e+01 232200 1
1730 4.350000e+00 4.084713e+00 1.705145e+01 233550 1
1740 4.518750e+00 4.084713e+00 1.716658e+01 234900 1
1750 5.500000e+00 4.084713e+00 1.729505e+01 236250 1
1760 4.925000e+00 4.084713e+00 1.742652e+01 237600 1
1770 4.350000e+00 4.084713e+00 1.755391e+01 238950 1
1780 3.731250e+00 4.084713e+00 1.767566e+01 240300 1
1790 5.025000e+00 4.084713e+00 1.779749e+01 241650 1
1800 4.100000e+00 4.084713e+00 1.791419e+01 243000 1
1810 3.200000e+00 4.084713e+00 1.803358e+01 244350 1
1820 2.937500e+00 4.084713e+00 1.819644e+01 245700 1
1830 5.200000e+00 4.084713e+00 1.836087e+01 247050 1
1840 3.225000e+00 4.084713e+00 1.848011e+01 248400 1
1850 4.000000e+00 4.084713e+00 1.859444e+01 249750 1
1860 3.525000e+00 4.084713e+00 1.871278e+01 251100 1
1870 4.050000e+00 4.084713e+00 1.883021e+01 252450 1
1880 3.150000e+00 4.084713e+00 1.894511e+01 253800 1
1890 3.187500e+00 4.084713e+00 1.907015e+01 255150 1
1900 4.612500e+00 4.084713e+00 1.919113e+01 256500 1
1910 3.600000e+00 4.084713e+00 1.931952e+01 257850 1
1920 3.875000e+00 4.084713e+00 1.943781e+01 259200 1
1930 5.325000e+00 4.084713e+00 1.958195e+01 260550 1
1940 4.187500e+00 4.084713e+00 1.969824e+01 261900 1
1950 3.325000e+00 4.084713e+00 1.981103e+01 263250 1
1960 3.187500e+00 4.084713e+00 1.993485e+01 264600 1
1966 5.250000e+00 4.084713e+00 2.000997e+01 265410 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.000997e+01
total solves : 265410
best bound : 4.084713e+00
numeric issues : 0
-------------------------------------------------------------------
-------------------------------------------------------------------
SDDP.jl (c) Oscar Dowson and contributors, 2017-26
-------------------------------------------------------------------
problem
nodes : 3
state variables : 1
scenarios : 8.51840e+04
existing cuts : false
options
solver : serial mode
risk measure : SDDP.Expectation()
sampling scheme : SDDP.InSampleMonteCarlo
subproblem structure
VariableRef : [6, 6]
AffExpr in MOI.EqualTo{Float64} : [1, 3]
AffExpr in MOI.LessThan{Float64} : [2, 2]
VariableRef in MOI.GreaterThan{Float64} : [3, 4]
VariableRef in MOI.LessThan{Float64} : [3, 3]
numerical stability report
matrix range [8e-01, 2e+00]
objective range [1e+00, 2e+00]
bounds range [1e+00, 1e+02]
rhs range [5e+01, 5e+01]
-------------------------------------------------------------------
iteration simulation bound time (s) solves pid
-------------------------------------------------------------------
10 5.325000e+00 8.837528e+00 1.033261e-01 1350 1
20 3.412500e+00 4.077081e+00 3.101661e-01 2700 1
30 4.300000e+00 4.070466e+00 6.109791e-01 4050 1
40 3.525000e+00 4.041705e+00 9.762340e-01 5400 1
50 3.675000e+00 4.039074e+00 1.380859e+00 6750 1
60 3.062500e+00 4.038574e+00 1.809727e+00 8100 1
70 4.937500e+00 4.038282e+00 2.301595e+00 9450 1
80 5.287500e+00 4.038276e+00 2.857545e+00 10800 1
90 4.575000e+00 4.038250e+00 3.532096e+00 12150 1
100 2.525000e+00 4.037860e+00 4.212171e+00 13500 1
110 5.175000e+00 4.037794e+00 4.984311e+00 14850 1
120 2.662500e+00 4.037794e+00 5.845810e+00 16200 1
130 5.375000e+00 4.037794e+00 6.785215e+00 17550 1
140 3.381250e+00 4.037794e+00 7.694120e+00 18900 1
150 2.856250e+00 4.037794e+00 8.638283e+00 20250 1
160 4.337500e+00 4.037786e+00 9.679471e+00 21600 1
170 3.875000e+00 4.037786e+00 1.073854e+01 22950 1
180 4.575000e+00 4.037786e+00 1.187840e+01 24300 1
190 5.300000e+00 4.037786e+00 1.302642e+01 25650 1
200 5.325000e+00 4.037786e+00 1.426529e+01 27000 1
210 3.437500e+00 4.037786e+00 1.551473e+01 28350 1
220 4.350000e+00 4.037786e+00 1.696617e+01 29700 1
230 3.937500e+00 4.037786e+00 1.838996e+01 31050 1
240 3.518750e+00 4.037786e+00 1.980787e+01 32400 1
242 3.525000e+00 4.037786e+00 2.008673e+01 32670 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.008673e+01
total solves : 32670
best bound : 4.037786e+00
numeric issues : 0
-------------------------------------------------------------------