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 8.509707e-02 1350 1
20 4.062500e+00 4.451907e+00 1.210949e-01 2700 1
30 2.993750e+00 4.101372e+00 1.605649e-01 4050 1
40 5.750000e+00 4.095757e+00 2.027240e-01 5400 1
50 5.125000e+00 4.093536e+00 2.470529e-01 6750 1
60 3.737500e+00 4.089225e+00 2.950220e-01 8100 1
70 4.500000e+00 4.088152e+00 3.420689e-01 9450 1
80 4.950000e+00 4.087904e+00 3.906429e-01 10800 1
90 4.125000e+00 4.087756e+00 4.409239e-01 12150 1
100 3.275000e+00 4.086300e+00 4.959331e-01 13500 1
110 5.250000e+00 4.086125e+00 5.497310e-01 14850 1
120 4.975000e+00 4.086054e+00 6.061699e-01 16200 1
130 3.500000e+00 4.085422e+00 6.611519e-01 17550 1
140 4.593750e+00 4.085327e+00 7.158000e-01 18900 1
150 3.000000e+00 4.085258e+00 1.133084e+00 20250 1
160 2.700000e+00 4.085247e+00 1.193537e+00 21600 1
170 3.812500e+00 4.085151e+00 1.253520e+00 22950 1
180 3.875000e+00 4.085121e+00 1.316248e+00 24300 1
190 4.737500e+00 4.085102e+00 1.376673e+00 25650 1
200 2.906250e+00 4.085073e+00 1.438061e+00 27000 1
210 3.750000e+00 4.085050e+00 1.502044e+00 28350 1
220 5.050000e+00 4.085037e+00 1.565733e+00 29700 1
230 2.925000e+00 4.085012e+00 1.627758e+00 31050 1
240 4.500000e+00 4.084970e+00 1.692931e+00 32400 1
250 4.875000e+00 4.084908e+00 1.761086e+00 33750 1
260 3.675000e+00 4.084905e+00 1.824244e+00 35100 1
270 4.725000e+00 4.084903e+00 1.890905e+00 36450 1
280 3.437500e+00 4.084900e+00 1.956095e+00 37800 1
290 3.750000e+00 4.084879e+00 2.024526e+00 39150 1
300 4.125000e+00 4.084879e+00 2.092891e+00 40500 1
310 4.875000e+00 4.084803e+00 2.159450e+00 41850 1
320 5.625000e+00 4.084803e+00 2.224747e+00 43200 1
330 3.825000e+00 4.084800e+00 2.292736e+00 44550 1
340 3.300000e+00 4.084796e+00 2.361451e+00 45900 1
350 5.887500e+00 4.084796e+00 2.431991e+00 47250 1
360 3.600000e+00 4.084786e+00 2.502157e+00 48600 1
370 3.618750e+00 4.084786e+00 2.569524e+00 49950 1
380 4.968750e+00 4.084782e+00 2.637450e+00 51300 1
390 3.300000e+00 4.084780e+00 2.703840e+00 52650 1
400 4.006250e+00 4.084779e+00 2.776143e+00 54000 1
410 4.050000e+00 4.084779e+00 2.849081e+00 55350 1
420 5.125000e+00 4.084776e+00 2.920658e+00 56700 1
430 4.000000e+00 4.084776e+00 2.992247e+00 58050 1
440 4.125000e+00 4.084776e+00 3.067300e+00 59400 1
450 3.112500e+00 4.084776e+00 3.143408e+00 60750 1
460 3.750000e+00 4.084771e+00 3.218369e+00 62100 1
470 3.187500e+00 4.084767e+00 3.287180e+00 63450 1
480 3.031250e+00 4.084757e+00 3.363995e+00 64800 1
490 4.181250e+00 4.084753e+00 3.437855e+00 66150 1
500 3.187500e+00 4.084746e+00 3.514691e+00 67500 1
510 4.875000e+00 4.084741e+00 3.588564e+00 68850 1
520 3.900000e+00 4.084737e+00 3.661919e+00 70200 1
530 4.350000e+00 4.084737e+00 3.737296e+00 71550 1
540 4.212500e+00 4.084737e+00 3.814647e+00 72900 1
550 4.250000e+00 4.084734e+00 3.894072e+00 74250 1
560 3.750000e+00 4.084734e+00 3.971271e+00 75600 1
570 5.306250e+00 4.084730e+00 4.048556e+00 76950 1
580 4.725000e+00 4.084730e+00 4.126358e+00 78300 1
590 4.250000e+00 4.084730e+00 4.203030e+00 79650 1
600 4.000000e+00 4.084730e+00 4.282302e+00 81000 1
610 4.600000e+00 4.084730e+00 4.357239e+00 82350 1
620 3.375000e+00 4.084730e+00 4.437999e+00 83700 1
630 3.981250e+00 4.084725e+00 4.560800e+00 85050 1
640 3.250000e+00 4.084725e+00 4.636657e+00 86400 1
650 3.625000e+00 4.084725e+00 4.710592e+00 87750 1
660 4.781250e+00 4.084725e+00 4.790140e+00 89100 1
670 4.275000e+00 4.084725e+00 4.869404e+00 90450 1
680 2.731250e+00 4.084725e+00 4.951912e+00 91800 1
690 5.237500e+00 4.084725e+00 5.033596e+00 93150 1
700 3.325000e+00 4.084725e+00 5.110028e+00 94500 1
710 4.750000e+00 4.084725e+00 5.192088e+00 95850 1
720 4.537500e+00 4.084725e+00 5.271530e+00 97200 1
730 4.725000e+00 4.084725e+00 5.353723e+00 98550 1
740 4.475000e+00 4.084725e+00 5.432584e+00 99900 1
750 2.893750e+00 4.084725e+00 5.512039e+00 101250 1
760 3.525000e+00 4.084725e+00 5.593519e+00 102600 1
770 3.525000e+00 4.084725e+00 5.676224e+00 103950 1
780 3.262500e+00 4.084725e+00 5.758627e+00 105300 1
790 4.918750e+00 4.084725e+00 5.845051e+00 106650 1
800 3.750000e+00 4.084725e+00 5.927360e+00 108000 1
810 4.687500e+00 4.084725e+00 6.009340e+00 109350 1
820 4.018750e+00 4.084725e+00 6.092539e+00 110700 1
830 4.725000e+00 4.084725e+00 6.175702e+00 112050 1
840 4.268750e+00 4.084725e+00 6.258430e+00 113400 1
850 5.175000e+00 4.084725e+00 6.337855e+00 114750 1
860 3.125000e+00 4.084725e+00 6.422701e+00 116100 1
870 2.762500e+00 4.084725e+00 6.500111e+00 117450 1
880 3.375000e+00 4.084725e+00 6.577511e+00 118800 1
890 3.875000e+00 4.084725e+00 6.660818e+00 120150 1
900 3.093750e+00 4.084725e+00 6.741138e+00 121500 1
910 4.125000e+00 4.084724e+00 6.830494e+00 122850 1
920 4.750000e+00 4.084724e+00 6.918762e+00 124200 1
930 5.431250e+00 4.084724e+00 7.004140e+00 125550 1
940 3.000000e+00 4.084724e+00 7.089449e+00 126900 1
950 4.243750e+00 4.084724e+00 7.171137e+00 128250 1
960 3.756250e+00 4.084724e+00 7.256038e+00 129600 1
970 3.750000e+00 4.084724e+00 7.343368e+00 130950 1
980 4.350000e+00 4.084724e+00 7.426637e+00 132300 1
990 3.375000e+00 4.084722e+00 7.511086e+00 133650 1
1000 4.750000e+00 4.084722e+00 7.594834e+00 135000 1
1010 3.825000e+00 4.084722e+00 7.677718e+00 136350 1
1020 4.000000e+00 4.084722e+00 7.757449e+00 137700 1
1030 4.500000e+00 4.084722e+00 7.842521e+00 139050 1
1040 3.637500e+00 4.084722e+00 7.927796e+00 140400 1
1050 4.050000e+00 4.084722e+00 8.012290e+00 141750 1
1060 4.925000e+00 4.084722e+00 8.125311e+00 143100 1
1070 4.500000e+00 4.084722e+00 8.213928e+00 144450 1
1080 5.000000e+00 4.084722e+00 8.304192e+00 145800 1
1090 4.393750e+00 4.084722e+00 8.391667e+00 147150 1
1100 3.750000e+00 4.084722e+00 8.484506e+00 148500 1
1110 4.306250e+00 4.084722e+00 8.570357e+00 149850 1
1120 4.200000e+00 4.084722e+00 8.660663e+00 151200 1
1130 4.343750e+00 4.084722e+00 8.751232e+00 152550 1
1140 4.650000e+00 4.084722e+00 8.842362e+00 153900 1
1150 4.537500e+00 4.084722e+00 8.933369e+00 155250 1
1160 4.250000e+00 4.084722e+00 9.025610e+00 156600 1
1170 3.312500e+00 4.084722e+00 9.114318e+00 157950 1
1180 4.968750e+00 4.084722e+00 9.204011e+00 159300 1
1190 4.062500e+00 4.084718e+00 9.297529e+00 160650 1
1200 3.750000e+00 4.084718e+00 9.387656e+00 162000 1
1210 4.387500e+00 4.084718e+00 9.477985e+00 163350 1
1220 5.237500e+00 4.084718e+00 9.577431e+00 164700 1
1230 2.737500e+00 4.084718e+00 9.665466e+00 166050 1
1240 4.587500e+00 4.084713e+00 9.757781e+00 167400 1
1250 3.750000e+00 4.084713e+00 9.848811e+00 168750 1
1260 4.250000e+00 4.084713e+00 9.943971e+00 170100 1
1270 4.125000e+00 4.084713e+00 1.003195e+01 171450 1
1280 4.125000e+00 4.084713e+00 1.012284e+01 172800 1
1290 4.250000e+00 4.084713e+00 1.021514e+01 174150 1
1300 3.350000e+00 4.084713e+00 1.030436e+01 175500 1
1310 4.187500e+00 4.084713e+00 1.039581e+01 176850 1
1320 3.437500e+00 4.084713e+00 1.048944e+01 178200 1
1330 3.731250e+00 4.084713e+00 1.058248e+01 179550 1
1340 5.250000e+00 4.084713e+00 1.068121e+01 180900 1
1350 4.750000e+00 4.084713e+00 1.077202e+01 182250 1
1360 4.725000e+00 4.084713e+00 1.086650e+01 183600 1
1370 4.150000e+00 4.084713e+00 1.095808e+01 184950 1
1380 3.287500e+00 4.084713e+00 1.105462e+01 186300 1
1390 4.875000e+00 4.084713e+00 1.115337e+01 187650 1
1400 3.075000e+00 4.084713e+00 1.124780e+01 189000 1
1410 3.875000e+00 4.084713e+00 1.134188e+01 190350 1
1420 5.662500e+00 4.084713e+00 1.144002e+01 191700 1
1430 3.550000e+00 4.084713e+00 1.155709e+01 193050 1
1440 4.687500e+00 4.084713e+00 1.165200e+01 194400 1
1450 3.243750e+00 4.084713e+00 1.174439e+01 195750 1
1460 3.250000e+00 4.084713e+00 1.183687e+01 197100 1
1470 3.250000e+00 4.084713e+00 1.193245e+01 198450 1
1480 4.075000e+00 4.084713e+00 1.202729e+01 199800 1
1490 3.200000e+00 4.084713e+00 1.212543e+01 201150 1
1500 3.406250e+00 4.084713e+00 1.222345e+01 202500 1
1510 4.593750e+00 4.084713e+00 1.232167e+01 203850 1
1520 3.750000e+00 4.084713e+00 1.242381e+01 205200 1
1530 4.637500e+00 4.084713e+00 1.252004e+01 206550 1
1540 4.125000e+00 4.084713e+00 1.261863e+01 207900 1
1550 4.875000e+00 4.084713e+00 1.271895e+01 209250 1
1560 3.437500e+00 4.084713e+00 1.281882e+01 210600 1
1570 4.293750e+00 4.084713e+00 1.291693e+01 211950 1
1580 4.500000e+00 4.084713e+00 1.301511e+01 213300 1
1590 4.350000e+00 4.084713e+00 1.311595e+01 214650 1
1600 4.575000e+00 4.084713e+00 1.321148e+01 216000 1
1610 3.175000e+00 4.084713e+00 1.331145e+01 217350 1
1620 2.625000e+00 4.084713e+00 1.341201e+01 218700 1
1630 4.750000e+00 4.084713e+00 1.351275e+01 220050 1
1640 3.625000e+00 4.084713e+00 1.361790e+01 221400 1
1650 4.375000e+00 4.084713e+00 1.371858e+01 222750 1
1660 3.700000e+00 4.084713e+00 1.381164e+01 224100 1
1670 3.625000e+00 4.084713e+00 1.390784e+01 225450 1
1680 3.750000e+00 4.084713e+00 1.400482e+01 226800 1
1690 3.700000e+00 4.084713e+00 1.409919e+01 228150 1
1700 4.125000e+00 4.084713e+00 1.420045e+01 229500 1
1710 5.093750e+00 4.084713e+00 1.429621e+01 230850 1
1720 4.500000e+00 4.084713e+00 1.439330e+01 232200 1
1730 4.350000e+00 4.084713e+00 1.449272e+01 233550 1
1740 4.518750e+00 4.084713e+00 1.458573e+01 234900 1
1750 5.500000e+00 4.084713e+00 1.469113e+01 236250 1
1760 4.925000e+00 4.084713e+00 1.479329e+01 237600 1
1770 4.350000e+00 4.084713e+00 1.491790e+01 238950 1
1780 3.731250e+00 4.084713e+00 1.501573e+01 240300 1
1790 5.025000e+00 4.084713e+00 1.511410e+01 241650 1
1800 4.100000e+00 4.084713e+00 1.520948e+01 243000 1
1810 3.200000e+00 4.084713e+00 1.530686e+01 244350 1
1820 2.937500e+00 4.084713e+00 1.540983e+01 245700 1
1830 5.200000e+00 4.084713e+00 1.551465e+01 247050 1
1840 3.225000e+00 4.084713e+00 1.561019e+01 248400 1
1850 4.000000e+00 4.084713e+00 1.570559e+01 249750 1
1860 3.525000e+00 4.084713e+00 1.580178e+01 251100 1
1870 4.050000e+00 4.084713e+00 1.589812e+01 252450 1
1880 3.150000e+00 4.084713e+00 1.599395e+01 253800 1
1890 3.187500e+00 4.084713e+00 1.609327e+01 255150 1
1900 4.612500e+00 4.084713e+00 1.618976e+01 256500 1
1910 3.600000e+00 4.084713e+00 1.629608e+01 257850 1
1920 3.875000e+00 4.084713e+00 1.639454e+01 259200 1
1930 5.325000e+00 4.084713e+00 1.649199e+01 260550 1
1940 4.187500e+00 4.084713e+00 1.659150e+01 261900 1
1950 3.325000e+00 4.084713e+00 1.668790e+01 263250 1
1960 3.187500e+00 4.084713e+00 1.679274e+01 264600 1
1970 5.250000e+00 4.084713e+00 1.689414e+01 265950 1
1980 4.225000e+00 4.084713e+00 1.698765e+01 267300 1
1990 3.312500e+00 4.084713e+00 1.708221e+01 268650 1
2000 4.087500e+00 4.084713e+00 1.718389e+01 270000 1
2010 3.681250e+00 4.084713e+00 1.728653e+01 271350 1
2020 4.900000e+00 4.084713e+00 1.738628e+01 272700 1
2030 2.812500e+00 4.084713e+00 1.747800e+01 274050 1
2040 5.343750e+00 4.084713e+00 1.757194e+01 275400 1
2050 4.500000e+00 4.084713e+00 1.766493e+01 276750 1
2060 3.525000e+00 4.084713e+00 1.776111e+01 278100 1
2070 4.275000e+00 4.084713e+00 1.785665e+01 279450 1
2080 4.375000e+00 4.084713e+00 1.795181e+01 280800 1
2090 3.775000e+00 4.084713e+00 1.805053e+01 282150 1
2100 4.000000e+00 4.084713e+00 1.816824e+01 283500 1
2110 4.350000e+00 4.084713e+00 1.827432e+01 284850 1
2120 4.250000e+00 4.084713e+00 1.837274e+01 286200 1
2130 3.862500e+00 4.084713e+00 1.846731e+01 287550 1
2140 3.350000e+00 4.084713e+00 1.856584e+01 288900 1
2150 5.625000e+00 4.084713e+00 1.866080e+01 290250 1
2160 3.750000e+00 4.084713e+00 1.875777e+01 291600 1
2170 3.150000e+00 4.084713e+00 1.885204e+01 292950 1
2180 3.412500e+00 4.084713e+00 1.894698e+01 294300 1
2190 3.750000e+00 4.084713e+00 1.904679e+01 295650 1
2200 3.837500e+00 4.084713e+00 1.914027e+01 297000 1
2210 3.675000e+00 4.084713e+00 1.923328e+01 298350 1
2220 3.025000e+00 4.084713e+00 1.932979e+01 299700 1
2230 3.000000e+00 4.084713e+00 1.943089e+01 301050 1
2240 3.331250e+00 4.084713e+00 1.953326e+01 302400 1
2250 4.312500e+00 4.084713e+00 1.963572e+01 303750 1
2260 5.250000e+00 4.084713e+00 1.974608e+01 305100 1
2270 3.937500e+00 4.084713e+00 1.984931e+01 306450 1
2280 5.625000e+00 4.084713e+00 1.995176e+01 307800 1
2285 3.375000e+00 4.084713e+00 2.000265e+01 308475 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.000265e+01
total solves : 308475
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 4.012500e+00 4.756591e+00 1.047158e-01 1350 1
20 3.693750e+00 4.062876e+00 2.752719e-01 2700 1
30 2.875000e+00 4.045081e+00 4.940069e-01 4050 1
40 4.031250e+00 4.043672e+00 7.744820e-01 5400 1
50 3.312500e+00 4.040909e+00 1.139680e+00 6750 1
60 3.850000e+00 4.040791e+00 1.556929e+00 8100 1
70 3.975000e+00 4.038294e+00 2.074164e+00 9450 1
80 4.350000e+00 4.038110e+00 2.617046e+00 10800 1
90 4.431250e+00 4.038087e+00 3.199992e+00 12150 1
100 4.218750e+00 4.038065e+00 3.866956e+00 13500 1
110 4.600000e+00 4.037710e+00 4.530438e+00 14850 1
120 3.975000e+00 4.037551e+00 5.265689e+00 16200 1
130 4.781250e+00 4.037555e+00 6.049854e+00 17550 1
140 3.437500e+00 4.037541e+00 6.880394e+00 18900 1
150 3.900000e+00 4.037546e+00 7.755365e+00 20250 1
160 4.750000e+00 4.037465e+00 8.659506e+00 21600 1
170 4.500000e+00 4.037468e+00 9.636149e+00 22950 1
180 4.087500e+00 4.037468e+00 1.063288e+01 24300 1
190 3.475000e+00 4.037353e+00 1.168334e+01 25650 1
200 3.843750e+00 4.037353e+00 1.284501e+01 27000 1
210 4.500000e+00 4.037353e+00 1.404098e+01 28350 1
220 4.793750e+00 4.037353e+00 1.524422e+01 29700 1
230 2.775000e+00 4.037353e+00 1.647902e+01 31050 1
240 4.500000e+00 4.037353e+00 1.773175e+01 32400 1
250 3.100000e+00 4.037353e+00 1.907038e+01 33750 1
257 5.200000e+00 4.037353e+00 2.002375e+01 34695 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.002375e+01
total solves : 34695
best bound : 4.037353e+00
numeric issues : 0
-------------------------------------------------------------------