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.915619e-01      1350   1
        20   4.062500e+00  4.451907e+00  2.880950e-01      2700   1
        30   2.993750e+00  4.101372e+00  3.939381e-01      4050   1
        40   5.750000e+00  4.095757e+00  5.048981e-01      5400   1
        50   5.125000e+00  4.093536e+00  6.208301e-01      6750   1
        60   3.737500e+00  4.089225e+00  7.442989e-01      8100   1
        70   4.500000e+00  4.088152e+00  8.678839e-01      9450   1
        80   4.950000e+00  4.087904e+00  9.939780e-01     10800   1
        90   4.125000e+00  4.087756e+00  1.124968e+00     12150   1
       100   3.275000e+00  4.086300e+00  1.265244e+00     13500   1
       110   5.250000e+00  4.086125e+00  1.399950e+00     14850   1
       120   4.975000e+00  4.086054e+00  1.542589e+00     16200   1
       130   3.500000e+00  4.085422e+00  1.681474e+00     17550   1
       140   4.593750e+00  4.085327e+00  1.820715e+00     18900   1
       150   3.000000e+00  4.085258e+00  1.959738e+00     20250   1
       160   2.700000e+00  4.085247e+00  2.129195e+00     21600   1
       170   3.812500e+00  4.085151e+00  2.273451e+00     22950   1
       180   3.875000e+00  4.085121e+00  2.423705e+00     24300   1
       190   4.737500e+00  4.085102e+00  2.568468e+00     25650   1
       200   2.906250e+00  4.085073e+00  2.715017e+00     27000   1
       210   3.750000e+00  4.085050e+00  2.866753e+00     28350   1
       220   5.050000e+00  4.085037e+00  3.015032e+00     29700   1
       230   2.925000e+00  4.085012e+00  3.158456e+00     31050   1
       240   4.500000e+00  4.084970e+00  3.308181e+00     32400   1
       250   4.875000e+00  4.084908e+00  3.464429e+00     33750   1
       260   3.675000e+00  4.084905e+00  3.609968e+00     35100   1
       270   4.725000e+00  4.084903e+00  3.766510e+00     36450   1
       280   3.437500e+00  4.084900e+00  3.917896e+00     37800   1
       290   3.750000e+00  4.084879e+00  4.076224e+00     39150   1
       300   4.125000e+00  4.084879e+00  4.237471e+00     40500   1
       310   4.875000e+00  4.084803e+00  4.393909e+00     41850   1
       320   5.625000e+00  4.084803e+00  4.547031e+00     43200   1
       330   3.825000e+00  4.084800e+00  4.708248e+00     44550   1
       340   3.300000e+00  4.084796e+00  4.868633e+00     45900   1
       350   5.887500e+00  4.084796e+00  5.057572e+00     47250   1
       360   3.600000e+00  4.084786e+00  5.220001e+00     48600   1
       370   3.618750e+00  4.084786e+00  5.377015e+00     49950   1
       380   4.968750e+00  4.084782e+00  5.532406e+00     51300   1
       390   3.300000e+00  4.084780e+00  5.689770e+00     52650   1
       400   4.006250e+00  4.084779e+00  5.856180e+00     54000   1
       410   4.050000e+00  4.084779e+00  6.025198e+00     55350   1
       420   5.125000e+00  4.084776e+00  6.189198e+00     56700   1
       430   4.000000e+00  4.084776e+00  6.352465e+00     58050   1
       440   4.125000e+00  4.084776e+00  6.520088e+00     59400   1
       450   3.112500e+00  4.084776e+00  6.689568e+00     60750   1
       460   3.750000e+00  4.084771e+00  6.857988e+00     62100   1
       470   3.187500e+00  4.084767e+00  7.014077e+00     63450   1
       480   3.031250e+00  4.084757e+00  7.197349e+00     64800   1
       490   4.181250e+00  4.084753e+00  7.368843e+00     66150   1
       500   3.187500e+00  4.084746e+00  7.546394e+00     67500   1
       510   4.875000e+00  4.084741e+00  7.715938e+00     68850   1
       520   3.900000e+00  4.084737e+00  7.880607e+00     70200   1
       530   4.350000e+00  4.084737e+00  8.049599e+00     71550   1
       540   4.212500e+00  4.084737e+00  8.236893e+00     72900   1
       550   4.250000e+00  4.084734e+00  8.409773e+00     74250   1
       560   3.750000e+00  4.084734e+00  8.579522e+00     75600   1
       570   5.306250e+00  4.084730e+00  8.750333e+00     76950   1
       580   4.725000e+00  4.084730e+00  8.920312e+00     78300   1
       590   4.250000e+00  4.084730e+00  9.088200e+00     79650   1
       600   4.000000e+00  4.084730e+00  9.261365e+00     81000   1
       610   4.600000e+00  4.084730e+00  9.424381e+00     82350   1
       620   3.375000e+00  4.084730e+00  9.592206e+00     83700   1
       630   3.981250e+00  4.084725e+00  9.767431e+00     85050   1
       640   3.250000e+00  4.084725e+00  9.938917e+00     86400   1
       650   3.625000e+00  4.084725e+00  1.012163e+01     87750   1
       660   4.781250e+00  4.084725e+00  1.030039e+01     89100   1
       670   4.275000e+00  4.084725e+00  1.048342e+01     90450   1
       680   2.731250e+00  4.084725e+00  1.067107e+01     91800   1
       690   5.237500e+00  4.084725e+00  1.085524e+01     93150   1
       700   3.325000e+00  4.084725e+00  1.102804e+01     94500   1
       710   4.750000e+00  4.084725e+00  1.121316e+01     95850   1
       720   4.537500e+00  4.084725e+00  1.139501e+01     97200   1
       730   4.725000e+00  4.084725e+00  1.159981e+01     98550   1
       740   4.475000e+00  4.084725e+00  1.177752e+01     99900   1
       750   2.893750e+00  4.084725e+00  1.195436e+01    101250   1
       760   3.525000e+00  4.084725e+00  1.213324e+01    102600   1
       770   3.525000e+00  4.084725e+00  1.231651e+01    103950   1
       780   3.262500e+00  4.084725e+00  1.249748e+01    105300   1
       790   4.918750e+00  4.084725e+00  1.268534e+01    106650   1
       800   3.750000e+00  4.084725e+00  1.286631e+01    108000   1
       810   4.687500e+00  4.084725e+00  1.304982e+01    109350   1
       820   4.018750e+00  4.084725e+00  1.323856e+01    110700   1
       830   4.725000e+00  4.084725e+00  1.342673e+01    112050   1
       840   4.268750e+00  4.084725e+00  1.361362e+01    113400   1
       850   5.175000e+00  4.084725e+00  1.379378e+01    114750   1
       860   3.125000e+00  4.084725e+00  1.398550e+01    116100   1
       870   2.762500e+00  4.084725e+00  1.416140e+01    117450   1
       880   3.375000e+00  4.084725e+00  1.433695e+01    118800   1
       890   3.875000e+00  4.084725e+00  1.454152e+01    120150   1
       900   3.093750e+00  4.084725e+00  1.472322e+01    121500   1
       910   4.125000e+00  4.084724e+00  1.492241e+01    122850   1
       920   4.750000e+00  4.084724e+00  1.511231e+01    124200   1
       930   5.431250e+00  4.084724e+00  1.530395e+01    125550   1
       940   3.000000e+00  4.084724e+00  1.549870e+01    126900   1
       950   4.243750e+00  4.084724e+00  1.568311e+01    128250   1
       960   3.756250e+00  4.084724e+00  1.586946e+01    129600   1
       970   3.750000e+00  4.084724e+00  1.606222e+01    130950   1
       980   4.350000e+00  4.084724e+00  1.624686e+01    132300   1
       990   3.375000e+00  4.084722e+00  1.643579e+01    133650   1
      1000   4.750000e+00  4.084722e+00  1.662216e+01    135000   1
      1010   3.825000e+00  4.084722e+00  1.680642e+01    136350   1
      1020   4.000000e+00  4.084722e+00  1.698178e+01    137700   1
      1030   4.500000e+00  4.084722e+00  1.716949e+01    139050   1
      1040   3.637500e+00  4.084722e+00  1.737693e+01    140400   1
      1050   4.050000e+00  4.084722e+00  1.756115e+01    141750   1
      1060   4.925000e+00  4.084722e+00  1.775640e+01    143100   1
      1070   4.500000e+00  4.084722e+00  1.795873e+01    144450   1
      1080   5.000000e+00  4.084722e+00  1.816278e+01    145800   1
      1090   4.393750e+00  4.084722e+00  1.836450e+01    147150   1
      1100   3.750000e+00  4.084722e+00  1.857728e+01    148500   1
      1110   4.306250e+00  4.084722e+00  1.876784e+01    149850   1
      1120   4.200000e+00  4.084722e+00  1.896592e+01    151200   1
      1130   4.343750e+00  4.084722e+00  1.916756e+01    152550   1
      1140   4.650000e+00  4.084722e+00  1.937020e+01    153900   1
      1150   4.537500e+00  4.084722e+00  1.957409e+01    155250   1
      1160   4.250000e+00  4.084722e+00  1.978398e+01    156600   1
      1170   3.312500e+00  4.084722e+00  2.000250e+01    157950   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.000250e+01
total solves   : 157950
best bound     :  4.084722e+00
simulation ci  :  4.099656e+00 ± 4.212180e-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   3.750000e+00  4.061415e+00  2.122209e-01      1350   1
        20   3.700000e+00  4.057843e+00  5.810919e-01      2700   1
        30   4.125000e+00  4.040573e+00  1.132602e+00      4050   1
        40   5.093750e+00  4.040141e+00  1.817626e+00      5400   1
        50   4.500000e+00  4.039277e+00  2.649579e+00      6750   1
        60   4.350000e+00  4.039145e+00  3.657843e+00      8100   1
        70   4.518750e+00  4.039125e+00  4.709006e+00      9450   1
        80   5.500000e+00  4.038974e+00  5.932834e+00     10800   1
        90   4.925000e+00  4.038841e+00  7.314723e+00     12150   1
       100   4.350000e+00  4.038773e+00  8.751976e+00     13500   1
       110   3.731250e+00  4.038221e+00  1.025620e+01     14850   1
       120   5.025000e+00  4.038153e+00  1.188265e+01     16200   1
       130   4.087500e+00  4.038131e+00  1.366521e+01     17550   1
       140   3.200000e+00  4.038117e+00  1.548993e+01     18900   1
       150   2.937500e+00  4.038116e+00  1.742603e+01     20250   1
       160   5.200000e+00  4.038097e+00  1.955540e+01     21600   1
       163   2.750000e+00  4.038097e+00  2.019301e+01     22005   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.019301e+01
total solves   : 22005
best bound     :  4.038097e+00
simulation ci  :  4.086081e+00 ± 1.144725e-01
numeric issues : 0
-------------------------------------------------------------------