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, Test
function 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[:]
end
function 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 ω
JuMP.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
return
end
newsvendor_example(; cut_type = SDDP.SINGLE_CUT)
newsvendor_example(; cut_type = SDDP.MULTI_CUT)-------------------------------------------------------------------
SDDP.jl (c) Oscar Dowson and contributors, 2017-25
-------------------------------------------------------------------
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.EqualTo{Float64} : [1, 1]
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.648669e-01 1350 1
20 4.062500e+00 4.451907e+00 2.451739e-01 2700 1
30 2.993750e+00 4.101372e+00 3.347261e-01 4050 1
40 5.750000e+00 4.095757e+00 4.293361e-01 5400 1
50 5.125000e+00 4.093536e+00 5.306690e-01 6750 1
60 3.737500e+00 4.089225e+00 6.360891e-01 8100 1
70 4.500000e+00 4.088152e+00 7.413409e-01 9450 1
80 4.950000e+00 4.087904e+00 8.536990e-01 10800 1
90 4.125000e+00 4.087756e+00 9.662449e-01 12150 1
100 3.275000e+00 4.086300e+00 1.086874e+00 13500 1
110 5.250000e+00 4.086125e+00 1.204738e+00 14850 1
120 4.975000e+00 4.086054e+00 1.329593e+00 16200 1
130 3.500000e+00 4.085422e+00 1.450783e+00 17550 1
140 4.593750e+00 4.085327e+00 1.574602e+00 18900 1
150 3.000000e+00 4.085258e+00 1.702631e+00 20250 1
160 2.700000e+00 4.085247e+00 1.836313e+00 21600 1
170 3.812500e+00 4.085151e+00 1.968387e+00 22950 1
180 3.875000e+00 4.085121e+00 2.107226e+00 24300 1
190 4.737500e+00 4.085102e+00 2.240217e+00 25650 1
200 2.906250e+00 4.085073e+00 2.378303e+00 27000 1
210 3.750000e+00 4.085050e+00 2.519181e+00 28350 1
220 5.050000e+00 4.085037e+00 2.657362e+00 29700 1
230 2.925000e+00 4.085012e+00 2.788957e+00 31050 1
240 4.500000e+00 4.084970e+00 2.927095e+00 32400 1
250 4.875000e+00 4.084908e+00 3.070455e+00 33750 1
260 3.675000e+00 4.084905e+00 3.202585e+00 35100 1
270 4.725000e+00 4.084903e+00 3.346268e+00 36450 1
280 3.437500e+00 4.084900e+00 3.484779e+00 37800 1
290 3.750000e+00 4.084879e+00 3.630241e+00 39150 1
300 4.125000e+00 4.084879e+00 3.778862e+00 40500 1
310 4.875000e+00 4.084803e+00 3.922713e+00 41850 1
320 5.625000e+00 4.084803e+00 4.063530e+00 43200 1
330 3.825000e+00 4.084800e+00 4.208812e+00 44550 1
340 3.300000e+00 4.084796e+00 4.355291e+00 45900 1
350 5.887500e+00 4.084796e+00 4.508543e+00 47250 1
360 3.600000e+00 4.084786e+00 4.662639e+00 48600 1
370 3.618750e+00 4.084786e+00 4.811166e+00 49950 1
380 4.968750e+00 4.084782e+00 4.956174e+00 51300 1
390 3.300000e+00 4.084780e+00 5.099273e+00 52650 1
400 4.006250e+00 4.084779e+00 5.252710e+00 54000 1
410 4.050000e+00 4.084779e+00 5.408424e+00 55350 1
420 5.125000e+00 4.084776e+00 5.559986e+00 56700 1
430 4.000000e+00 4.084776e+00 5.714226e+00 58050 1
440 4.125000e+00 4.084776e+00 5.871183e+00 59400 1
450 3.112500e+00 4.084776e+00 6.025212e+00 60750 1
460 3.750000e+00 4.084771e+00 6.179836e+00 62100 1
470 3.187500e+00 4.084767e+00 6.321124e+00 63450 1
480 3.031250e+00 4.084757e+00 6.484157e+00 64800 1
490 4.181250e+00 4.084753e+00 6.711332e+00 66150 1
500 3.187500e+00 4.084746e+00 6.868663e+00 67500 1
510 4.875000e+00 4.084741e+00 7.016357e+00 68850 1
520 3.900000e+00 4.084737e+00 7.160875e+00 70200 1
530 4.350000e+00 4.084737e+00 7.308208e+00 71550 1
540 4.212500e+00 4.084737e+00 7.455824e+00 72900 1
550 4.250000e+00 4.084734e+00 7.609197e+00 74250 1
560 3.750000e+00 4.084734e+00 7.768577e+00 75600 1
570 5.306250e+00 4.084730e+00 7.917809e+00 76950 1
580 4.725000e+00 4.084730e+00 8.067239e+00 78300 1
590 4.250000e+00 4.084730e+00 8.215182e+00 79650 1
600 4.000000e+00 4.084730e+00 8.370224e+00 81000 1
610 4.600000e+00 4.084730e+00 8.512295e+00 82350 1
620 3.375000e+00 4.084730e+00 8.662691e+00 83700 1
630 3.981250e+00 4.084725e+00 8.827349e+00 85050 1
640 3.250000e+00 4.084725e+00 8.976892e+00 86400 1
650 3.625000e+00 4.084725e+00 9.123791e+00 87750 1
660 4.781250e+00 4.084725e+00 9.273646e+00 89100 1
670 4.287500e+00 4.084725e+00 9.428571e+00 90450 1
680 2.731250e+00 4.084725e+00 9.584451e+00 91800 1
690 5.237500e+00 4.084725e+00 9.740046e+00 93150 1
700 3.325000e+00 4.084725e+00 9.891113e+00 94500 1
710 4.750000e+00 4.084725e+00 1.005209e+01 95850 1
720 4.537500e+00 4.084725e+00 1.020624e+01 97200 1
730 4.725000e+00 4.084725e+00 1.036815e+01 98550 1
740 4.475000e+00 4.084725e+00 1.052116e+01 99900 1
750 2.893750e+00 4.084725e+00 1.067404e+01 101250 1
760 3.525000e+00 4.084725e+00 1.083485e+01 102600 1
770 3.587500e+00 4.084725e+00 1.098856e+01 103950 1
780 3.262500e+00 4.084725e+00 1.114729e+01 105300 1
790 4.918750e+00 4.084725e+00 1.134384e+01 106650 1
800 3.750000e+00 4.084725e+00 1.149880e+01 108000 1
810 4.687500e+00 4.084725e+00 1.165907e+01 109350 1
820 4.018750e+00 4.084725e+00 1.182699e+01 110700 1
830 4.725000e+00 4.084725e+00 1.199201e+01 112050 1
840 4.268750e+00 4.084725e+00 1.215825e+01 113400 1
850 5.175000e+00 4.084725e+00 1.231607e+01 114750 1
860 3.125000e+00 4.084725e+00 1.248255e+01 116100 1
870 2.762500e+00 4.084725e+00 1.263614e+01 117450 1
880 3.375000e+00 4.084725e+00 1.278526e+01 118800 1
890 3.875000e+00 4.084725e+00 1.295212e+01 120150 1
900 3.093750e+00 4.084725e+00 1.310880e+01 121500 1
910 4.125000e+00 4.084724e+00 1.328153e+01 122850 1
920 4.750000e+00 4.084724e+00 1.344477e+01 124200 1
930 5.431250e+00 4.084724e+00 1.360631e+01 125550 1
940 3.000000e+00 4.084724e+00 1.376878e+01 126900 1
950 4.243750e+00 4.084724e+00 1.392766e+01 128250 1
960 3.756250e+00 4.084724e+00 1.408759e+01 129600 1
970 3.750000e+00 4.084724e+00 1.425397e+01 130950 1
980 4.350000e+00 4.084724e+00 1.441129e+01 132300 1
990 3.375000e+00 4.084722e+00 1.457466e+01 133650 1
1000 4.750000e+00 4.084722e+00 1.473260e+01 135000 1
1010 3.825000e+00 4.084722e+00 1.489277e+01 136350 1
1020 4.000000e+00 4.084722e+00 1.505087e+01 137700 1
1030 4.500000e+00 4.084722e+00 1.521810e+01 139050 1
1040 3.637500e+00 4.084722e+00 1.538367e+01 140400 1
1050 4.050000e+00 4.084722e+00 1.556446e+01 141750 1
1060 4.925000e+00 4.084722e+00 1.573048e+01 143100 1
1070 4.500000e+00 4.084722e+00 1.590314e+01 144450 1
1080 5.000000e+00 4.084722e+00 1.607980e+01 145800 1
1090 4.393750e+00 4.084722e+00 1.624742e+01 147150 1
1100 3.750000e+00 4.084722e+00 1.643294e+01 148500 1
1110 4.306250e+00 4.084722e+00 1.659488e+01 149850 1
1120 4.200000e+00 4.084722e+00 1.676193e+01 151200 1
1130 4.343750e+00 4.084722e+00 1.693606e+01 152550 1
1140 4.637500e+00 4.084722e+00 1.710913e+01 153900 1
1150 4.537500e+00 4.084722e+00 1.728421e+01 155250 1
1160 4.250000e+00 4.084722e+00 1.745990e+01 156600 1
1170 3.312500e+00 4.084722e+00 1.762582e+01 157950 1
1180 4.968750e+00 4.084722e+00 1.779420e+01 159300 1
1190 4.062500e+00 4.084718e+00 1.796964e+01 160650 1
1200 3.750000e+00 4.084718e+00 1.814402e+01 162000 1
1210 4.387500e+00 4.084718e+00 1.831868e+01 163350 1
1220 5.237500e+00 4.084718e+00 1.850383e+01 164700 1
1230 2.737500e+00 4.084718e+00 1.866961e+01 166050 1
1240 4.587500e+00 4.084713e+00 1.884321e+01 167400 1
1250 3.787500e+00 4.084713e+00 1.901462e+01 168750 1
1260 4.250000e+00 4.084713e+00 1.919264e+01 170100 1
1270 4.125000e+00 4.084713e+00 1.938233e+01 171450 1
1280 4.125000e+00 4.084713e+00 1.955444e+01 172800 1
1290 4.250000e+00 4.084713e+00 1.972691e+01 174150 1
1300 3.350000e+00 4.084713e+00 1.989781e+01 175500 1
1306 4.043750e+00 4.084713e+00 2.000239e+01 176310 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.000239e+01
total solves : 176310
best bound : 4.084713e+00
simulation ci : 4.100386e+00 ± 4.006491e-02
numeric issues : 0
-------------------------------------------------------------------
-------------------------------------------------------------------
SDDP.jl (c) Oscar Dowson and contributors, 2017-25
-------------------------------------------------------------------
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.EqualTo{Float64} : [1, 1]
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 2.662500e+00 4.067422e+00 1.781240e-01 1350 1
20 4.725000e+00 4.057856e+00 5.184929e-01 2700 1
30 3.993750e+00 4.041576e+00 9.942949e-01 4050 1
40 4.825000e+00 4.039977e+00 1.590457e+00 5400 1
50 4.068750e+00 4.039126e+00 2.331145e+00 6750 1
60 4.750000e+00 4.038817e+00 3.186409e+00 8100 1
70 3.087500e+00 4.037588e+00 4.162917e+00 9450 1
80 3.975000e+00 4.037565e+00 5.305077e+00 10800 1
90 3.675000e+00 4.037478e+00 6.553275e+00 12150 1
100 2.981250e+00 4.037483e+00 7.835035e+00 13500 1
110 4.125000e+00 4.037483e+00 9.300893e+00 14850 1
120 5.750000e+00 4.037443e+00 1.076818e+01 16200 1
130 4.750000e+00 4.037398e+00 1.236348e+01 17550 1
140 3.537500e+00 4.037398e+00 1.409116e+01 18900 1
150 4.500000e+00 4.037398e+00 1.600131e+01 20250 1
160 5.250000e+00 4.037213e+00 1.798802e+01 21600 1
170 3.937500e+00 4.037213e+00 2.004198e+01 22950 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.004198e+01
total solves : 22950
best bound : 4.037213e+00
simulation ci : 3.991124e+00 ± 1.109252e-01
numeric issues : 0
-------------------------------------------------------------------