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-24
-------------------------------------------------------------------
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.250000e+00 4.888859e+00 1.623690e-01 1350 1
20 4.350000e+00 4.105855e+00 2.459061e-01 2700 1
30 5.000000e+00 4.100490e+00 3.396561e-01 4050 1
40 3.500000e+00 4.097376e+00 4.380360e-01 5400 1
50 5.250000e+00 4.095859e+00 5.418730e-01 6750 1
60 3.643750e+00 4.093342e+00 6.494570e-01 8100 1
70 2.643750e+00 4.091818e+00 7.563381e-01 9450 1
80 5.087500e+00 4.091591e+00 8.653121e-01 10800 1
90 5.062500e+00 4.091309e+00 9.759631e-01 12150 1
100 4.843750e+00 4.087004e+00 1.096691e+00 13500 1
110 3.437500e+00 4.086094e+00 1.221343e+00 14850 1
120 3.375000e+00 4.085926e+00 1.406045e+00 16200 1
130 5.025000e+00 4.085866e+00 1.527503e+00 17550 1
140 5.000000e+00 4.085734e+00 1.648967e+00 18900 1
150 3.500000e+00 4.085655e+00 1.772706e+00 20250 1
160 4.281250e+00 4.085454e+00 1.893141e+00 21600 1
170 4.562500e+00 4.085425e+00 2.017000e+00 22950 1
180 5.768750e+00 4.085425e+00 2.140379e+00 24300 1
190 3.468750e+00 4.085359e+00 2.270954e+00 25650 1
200 4.131250e+00 4.085225e+00 2.399533e+00 27000 1
210 4.512500e+00 4.085157e+00 2.525849e+00 28350 1
220 4.900000e+00 4.085153e+00 2.653130e+00 29700 1
230 4.025000e+00 4.085134e+00 2.784696e+00 31050 1
240 4.468750e+00 4.085116e+00 2.919173e+00 32400 1
250 4.062500e+00 4.085075e+00 3.051067e+00 33750 1
260 4.875000e+00 4.085037e+00 3.185601e+00 35100 1
270 3.850000e+00 4.085011e+00 3.322380e+00 36450 1
280 4.912500e+00 4.084992e+00 3.458672e+00 37800 1
290 2.987500e+00 4.084986e+00 3.599919e+00 39150 1
300 3.825000e+00 4.084957e+00 3.743495e+00 40500 1
310 3.250000e+00 4.084911e+00 3.887602e+00 41850 1
320 3.600000e+00 4.084896e+00 4.065065e+00 43200 1
330 3.925000e+00 4.084896e+00 4.195889e+00 44550 1
340 4.500000e+00 4.084893e+00 4.337054e+00 45900 1
350 5.000000e+00 4.084891e+00 4.477218e+00 47250 1
360 3.075000e+00 4.084866e+00 4.616141e+00 48600 1
370 3.500000e+00 4.084861e+00 4.761287e+00 49950 1
380 3.356250e+00 4.084857e+00 4.909181e+00 51300 1
390 5.500000e+00 4.084846e+00 5.063323e+00 52650 1
400 4.475000e+00 4.084846e+00 5.208159e+00 54000 1
410 3.750000e+00 4.084843e+00 5.362206e+00 55350 1
420 3.687500e+00 4.084843e+00 5.512268e+00 56700 1
430 4.337500e+00 4.084825e+00 5.663661e+00 58050 1
440 5.750000e+00 4.084825e+00 5.799581e+00 59400 1
450 4.925000e+00 4.084792e+00 5.952962e+00 60750 1
460 3.600000e+00 4.084792e+00 6.102822e+00 62100 1
470 4.387500e+00 4.084792e+00 6.249562e+00 63450 1
480 4.000000e+00 4.084792e+00 6.412821e+00 64800 1
490 2.975000e+00 4.084788e+00 6.562707e+00 66150 1
500 3.125000e+00 4.084788e+00 6.717307e+00 67500 1
510 4.250000e+00 4.084788e+00 6.874574e+00 68850 1
520 4.512500e+00 4.084786e+00 7.045290e+00 70200 1
530 3.875000e+00 4.084786e+00 7.202519e+00 71550 1
540 4.387500e+00 4.084781e+00 7.358643e+00 72900 1
550 5.281250e+00 4.084780e+00 7.526423e+00 74250 1
560 4.650000e+00 4.084780e+00 7.672789e+00 75600 1
570 3.062500e+00 4.084780e+00 7.822330e+00 76950 1
580 3.187500e+00 4.084780e+00 7.967810e+00 78300 1
590 3.812500e+00 4.084780e+00 8.110718e+00 79650 1
600 3.637500e+00 4.084774e+00 8.264540e+00 81000 1
610 3.950000e+00 4.084765e+00 8.415624e+00 82350 1
620 4.625000e+00 4.084760e+00 8.568368e+00 83700 1
630 4.218750e+00 4.084760e+00 8.724727e+00 85050 1
640 3.025000e+00 4.084755e+00 8.878403e+00 86400 1
650 2.993750e+00 4.084751e+00 9.026021e+00 87750 1
660 3.262500e+00 4.084746e+00 9.177057e+00 89100 1
670 3.625000e+00 4.084746e+00 9.332709e+00 90450 1
680 2.981250e+00 4.084746e+00 9.492890e+00 91800 1
690 4.187500e+00 4.084746e+00 9.646070e+00 93150 1
700 4.500000e+00 4.084746e+00 9.820708e+00 94500 1
710 3.225000e+00 4.084746e+00 9.973517e+00 95850 1
720 4.375000e+00 4.084746e+00 1.012858e+01 97200 1
730 2.650000e+00 4.084746e+00 1.028919e+01 98550 1
740 3.250000e+00 4.084746e+00 1.044312e+01 99900 1
750 4.725000e+00 4.084746e+00 1.062022e+01 101250 1
760 3.375000e+00 4.084746e+00 1.078725e+01 102600 1
770 5.375000e+00 4.084746e+00 1.095120e+01 103950 1
780 4.068750e+00 4.084746e+00 1.112215e+01 105300 1
790 4.412500e+00 4.084746e+00 1.129572e+01 106650 1
800 4.350000e+00 4.084746e+00 1.146370e+01 108000 1
810 5.887500e+00 4.084746e+00 1.164036e+01 109350 1
820 4.912500e+00 4.084746e+00 1.180258e+01 110700 1
830 4.387500e+00 4.084746e+00 1.195811e+01 112050 1
840 3.675000e+00 4.084746e+00 1.212303e+01 113400 1
850 5.375000e+00 4.084746e+00 1.228404e+01 114750 1
860 3.562500e+00 4.084746e+00 1.245393e+01 116100 1
870 3.075000e+00 4.084746e+00 1.265307e+01 117450 1
880 3.625000e+00 4.084746e+00 1.281650e+01 118800 1
890 2.937500e+00 4.084746e+00 1.297552e+01 120150 1
900 4.450000e+00 4.084746e+00 1.314462e+01 121500 1
910 4.200000e+00 4.084746e+00 1.331029e+01 122850 1
920 3.687500e+00 4.084746e+00 1.348291e+01 124200 1
930 4.725000e+00 4.084746e+00 1.366160e+01 125550 1
940 4.018750e+00 4.084746e+00 1.382344e+01 126900 1
950 4.675000e+00 4.084746e+00 1.398385e+01 128250 1
960 3.375000e+00 4.084746e+00 1.414526e+01 129600 1
970 3.812500e+00 4.084746e+00 1.430265e+01 130950 1
980 3.112500e+00 4.084746e+00 1.446558e+01 132300 1
990 3.600000e+00 4.084746e+00 1.463080e+01 133650 1
1000 5.500000e+00 4.084746e+00 1.479837e+01 135000 1
1010 3.187500e+00 4.084746e+00 1.496076e+01 136350 1
1020 4.900000e+00 4.084746e+00 1.512542e+01 137700 1
1030 3.637500e+00 4.084746e+00 1.532644e+01 139050 1
1040 3.975000e+00 4.084746e+00 1.549330e+01 140400 1
1050 4.750000e+00 4.084746e+00 1.566536e+01 141750 1
1060 4.437500e+00 4.084746e+00 1.585084e+01 143100 1
1070 5.000000e+00 4.084746e+00 1.602452e+01 144450 1
1080 4.143750e+00 4.084746e+00 1.619935e+01 145800 1
1090 5.625000e+00 4.084746e+00 1.636502e+01 147150 1
1100 3.475000e+00 4.084746e+00 1.653872e+01 148500 1
1110 4.156250e+00 4.084746e+00 1.671999e+01 149850 1
1120 4.450000e+00 4.084746e+00 1.689455e+01 151200 1
1130 3.312500e+00 4.084741e+00 1.707436e+01 152550 1
1140 5.375000e+00 4.084741e+00 1.724161e+01 153900 1
1150 4.800000e+00 4.084737e+00 1.742168e+01 155250 1
1160 3.300000e+00 4.084737e+00 1.761647e+01 156600 1
1170 4.356250e+00 4.084737e+00 1.779288e+01 157950 1
1180 3.900000e+00 4.084737e+00 1.797398e+01 159300 1
1190 4.450000e+00 4.084737e+00 1.815479e+01 160650 1
1200 5.156250e+00 4.084737e+00 1.833632e+01 162000 1
1210 4.500000e+00 4.084737e+00 1.850441e+01 163350 1
1220 4.875000e+00 4.084737e+00 1.869282e+01 164700 1
1230 4.000000e+00 4.084737e+00 1.886835e+01 166050 1
1240 4.062500e+00 4.084737e+00 1.904491e+01 167400 1
1250 5.450000e+00 4.084737e+00 1.922506e+01 168750 1
1260 4.500000e+00 4.084737e+00 1.940641e+01 170100 1
1270 4.125000e+00 4.084737e+00 1.958693e+01 171450 1
1280 3.750000e+00 4.084737e+00 1.979442e+01 172800 1
1290 4.475000e+00 4.084737e+00 1.997296e+01 174150 1
1292 5.325000e+00 4.084737e+00 2.000751e+01 174420 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.000751e+01
total solves : 174420
best bound : 4.084737e+00
simulation ci : 4.072036e+00 ± 3.989332e-02
numeric issues : 0
-------------------------------------------------------------------
-------------------------------------------------------------------
SDDP.jl (c) Oscar Dowson and contributors, 2017-24
-------------------------------------------------------------------
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 3.687500e+00 7.731319e+00 1.719990e-01 1350 1
20 2.987500e+00 6.035682e+00 5.157661e-01 2700 1
30 3.225000e+00 4.731188e+00 9.660611e-01 4050 1
40 4.500000e+00 4.727832e+00 1.507689e+00 5400 1
50 5.750000e+00 4.042977e+00 2.112304e+00 6750 1
60 3.693750e+00 4.042133e+00 2.843256e+00 8100 1
70 3.800000e+00 4.041204e+00 3.686171e+00 9450 1
80 2.687500e+00 4.040929e+00 4.616398e+00 10800 1
90 4.737500e+00 4.040882e+00 5.751779e+00 12150 1
100 4.550000e+00 4.040650e+00 7.024384e+00 13500 1
110 3.250000e+00 4.039597e+00 8.315299e+00 14850 1
120 3.062500e+00 4.039547e+00 9.775433e+00 16200 1
130 3.750000e+00 4.037600e+00 1.131519e+01 17550 1
140 4.262500e+00 4.037640e+00 1.298260e+01 18900 1
150 3.243750e+00 4.037557e+00 1.473891e+01 20250 1
160 5.537500e+00 4.037553e+00 1.667345e+01 21600 1
170 3.312500e+00 4.037523e+00 1.876429e+01 22950 1
177 4.781250e+00 4.037530e+00 2.016455e+01 23895 1
-------------------------------------------------------------------
status : time_limit
total time (s) : 2.016455e+01
total solves : 23895
best bound : 4.037530e+00
simulation ci : 4.003884e+00 ± 1.169699e-01
numeric issues : 0
-------------------------------------------------------------------