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.250000e+00  4.888859e+00  1.703231e-01      1350   1
        20   4.350000e+00  4.105855e+00  2.545590e-01      2700   1
        30   5.000000e+00  4.100490e+00  3.498201e-01      4050   1
        40   3.475000e+00  4.097376e+00  4.529400e-01      5400   1
        50   5.250000e+00  4.095862e+00  5.609651e-01      6750   1
        60   3.643750e+00  4.093345e+00  6.741240e-01      8100   1
        70   2.643750e+00  4.091824e+00  7.854090e-01      9450   1
        80   5.087500e+00  4.091594e+00  8.994031e-01     10800   1
        90   5.062500e+00  4.091314e+00  1.012594e+00     12150   1
       100   4.843750e+00  4.086999e+00  1.137686e+00     13500   1
       110   3.437500e+00  4.086095e+00  1.262119e+00     14850   1
       120   3.375000e+00  4.085928e+00  1.388808e+00     16200   1
       130   5.025000e+00  4.085864e+00  1.520629e+00     17550   1
       140   5.000000e+00  4.085733e+00  1.653978e+00     18900   1
       150   3.500000e+00  4.085659e+00  1.787290e+00     20250   1
       160   4.281250e+00  4.085459e+00  1.916671e+00     21600   1
       170   4.500000e+00  4.085433e+00  2.047967e+00     22950   1
       180   5.768750e+00  4.085431e+00  2.181819e+00     24300   1
       190   3.468750e+00  4.085369e+00  2.323833e+00     25650   1
       200   4.131250e+00  4.085231e+00  2.463912e+00     27000   1
       210   4.506250e+00  4.085165e+00  2.601419e+00     28350   1
       220   4.900000e+00  4.085162e+00  2.744098e+00     29700   1
       230   4.025000e+00  4.085143e+00  2.884650e+00     31050   1
       240   4.468750e+00  4.085124e+00  3.031116e+00     32400   1
       250   4.062500e+00  4.085084e+00  3.176384e+00     33750   1
       260   4.875000e+00  4.085047e+00  3.321893e+00     35100   1
       270   3.850000e+00  4.085019e+00  3.466914e+00     36450   1
       280   4.912500e+00  4.085000e+00  3.616541e+00     37800   1
       290   2.987500e+00  4.084993e+00  3.770007e+00     39150   1
       300   3.825000e+00  4.084961e+00  3.919788e+00     40500   1
       310   3.250000e+00  4.084914e+00  4.071338e+00     41850   1
       320   3.537500e+00  4.084897e+00  4.228617e+00     43200   1
       330   3.950000e+00  4.084897e+00  4.372899e+00     44550   1
       340   4.500000e+00  4.084895e+00  4.522618e+00     45900   1
       350   5.000000e+00  4.084893e+00  4.674720e+00     47250   1
       360   3.075000e+00  4.084867e+00  4.829082e+00     48600   1
       370   3.500000e+00  4.084862e+00  4.992973e+00     49950   1
       380   3.356250e+00  4.084857e+00  5.169404e+00     51300   1
       390   5.500000e+00  4.084841e+00  5.341658e+00     52650   1
       400   4.475000e+00  4.084837e+00  5.505488e+00     54000   1
       410   3.750000e+00  4.084834e+00  5.667942e+00     55350   1
       420   3.687500e+00  4.084834e+00  5.835109e+00     56700   1
       430   4.337500e+00  4.084813e+00  5.997318e+00     58050   1
       440   5.750000e+00  4.084813e+00  6.139562e+00     59400   1
       450   4.937500e+00  4.084776e+00  6.303479e+00     60750   1
       460   3.600000e+00  4.084776e+00  6.464023e+00     62100   1
       470   4.387500e+00  4.084776e+00  6.617938e+00     63450   1
       480   4.000000e+00  4.084771e+00  6.843878e+00     64800   1
       490   2.975000e+00  4.084769e+00  6.994773e+00     66150   1
       500   3.125000e+00  4.084769e+00  7.143525e+00     67500   1
       510   4.250000e+00  4.084769e+00  7.301969e+00     68850   1
       520   4.512500e+00  4.084767e+00  7.450155e+00     70200   1
       530   3.875000e+00  4.084767e+00  7.608479e+00     71550   1
       540   4.387500e+00  4.084762e+00  7.768783e+00     72900   1
       550   5.287500e+00  4.084762e+00  7.928247e+00     74250   1
       560   4.650000e+00  4.084762e+00  8.078616e+00     75600   1
       570   3.062500e+00  4.084762e+00  8.235608e+00     76950   1
       580   3.187500e+00  4.084758e+00  8.382102e+00     78300   1
       590   3.812500e+00  4.084758e+00  8.523037e+00     79650   1
       600   3.637500e+00  4.084746e+00  8.671727e+00     81000   1
       610   3.925000e+00  4.084746e+00  8.821481e+00     82350   1
       620   4.625000e+00  4.084746e+00  8.978642e+00     83700   1
       630   4.218750e+00  4.084746e+00  9.139450e+00     85050   1
       640   3.025000e+00  4.084746e+00  9.291876e+00     86400   1
       650   2.993750e+00  4.084746e+00  9.436868e+00     87750   1
       660   3.262500e+00  4.084746e+00  9.587109e+00     89100   1
       670   3.575000e+00  4.084746e+00  9.742890e+00     90450   1
       680   2.981250e+00  4.084746e+00  9.900750e+00     91800   1
       690   4.187500e+00  4.084746e+00  1.005795e+01     93150   1
       700   4.500000e+00  4.084746e+00  1.021269e+01     94500   1
       710   3.225000e+00  4.084746e+00  1.036717e+01     95850   1
       720   4.375000e+00  4.084746e+00  1.052278e+01     97200   1
       730   2.650000e+00  4.084746e+00  1.068308e+01     98550   1
       740   3.312500e+00  4.084746e+00  1.083623e+01     99900   1
       750   4.725000e+00  4.084746e+00  1.100559e+01    101250   1
       760   3.375000e+00  4.084746e+00  1.117214e+01    102600   1
       770   5.375000e+00  4.084746e+00  1.136401e+01    103950   1
       780   4.068750e+00  4.084746e+00  1.152868e+01    105300   1
       790   4.412500e+00  4.084746e+00  1.169374e+01    106650   1
       800   4.350000e+00  4.084746e+00  1.185968e+01    108000   1
       810   5.887500e+00  4.084746e+00  1.203275e+01    109350   1
       820   4.912500e+00  4.084746e+00  1.219914e+01    110700   1
       830   4.400000e+00  4.084746e+00  1.236000e+01    112050   1
       840   3.675000e+00  4.084746e+00  1.253118e+01    113400   1
       850   5.375000e+00  4.084746e+00  1.269245e+01    114750   1
       860   3.562500e+00  4.084746e+00  1.286618e+01    116100   1
       870   3.075000e+00  4.084746e+00  1.304894e+01    117450   1
       880   3.625000e+00  4.084746e+00  1.322153e+01    118800   1
       890   2.937500e+00  4.084746e+00  1.338923e+01    120150   1
       900   4.450000e+00  4.084746e+00  1.356215e+01    121500   1
       910   4.200000e+00  4.084746e+00  1.373452e+01    122850   1
       920   3.687500e+00  4.084746e+00  1.390866e+01    124200   1
       930   4.725000e+00  4.084746e+00  1.408534e+01    125550   1
       940   4.018750e+00  4.084746e+00  1.424760e+01    126900   1
       950   4.675000e+00  4.084746e+00  1.441021e+01    128250   1
       960   3.375000e+00  4.084746e+00  1.456833e+01    129600   1
       970   3.812500e+00  4.084746e+00  1.472504e+01    130950   1
       980   3.112500e+00  4.084746e+00  1.488442e+01    132300   1
       990   3.600000e+00  4.084746e+00  1.504916e+01    133650   1
      1000   5.500000e+00  4.084746e+00  1.522439e+01    135000   1
      1010   3.187500e+00  4.084746e+00  1.539386e+01    136350   1
      1020   4.900000e+00  4.084746e+00  1.556412e+01    137700   1
      1030   3.637500e+00  4.084746e+00  1.576320e+01    139050   1
      1040   3.975000e+00  4.084746e+00  1.593088e+01    140400   1
      1050   4.750000e+00  4.084746e+00  1.610799e+01    141750   1
      1060   4.437500e+00  4.084746e+00  1.630352e+01    143100   1
      1070   5.000000e+00  4.084746e+00  1.649109e+01    144450   1
      1080   4.143750e+00  4.084746e+00  1.667578e+01    145800   1
      1090   5.625000e+00  4.084746e+00  1.684394e+01    147150   1
      1100   3.475000e+00  4.084746e+00  1.702663e+01    148500   1
      1110   4.156250e+00  4.084746e+00  1.722313e+01    149850   1
      1120   4.450000e+00  4.084746e+00  1.740500e+01    151200   1
      1130   3.225000e+00  4.084741e+00  1.759124e+01    152550   1
      1140   5.375000e+00  4.084741e+00  1.776801e+01    153900   1
      1150   4.800000e+00  4.084737e+00  1.795543e+01    155250   1
      1160   3.300000e+00  4.084737e+00  1.813388e+01    156600   1
      1170   4.356250e+00  4.084737e+00  1.830880e+01    157950   1
      1180   3.906250e+00  4.084737e+00  1.849088e+01    159300   1
      1190   4.450000e+00  4.084737e+00  1.867919e+01    160650   1
      1200   5.156250e+00  4.084737e+00  1.886982e+01    162000   1
      1210   4.512500e+00  4.084737e+00  1.904650e+01    163350   1
      1220   4.875000e+00  4.084737e+00  1.926233e+01    164700   1
      1230   4.000000e+00  4.084737e+00  1.944005e+01    166050   1
      1240   4.050000e+00  4.084737e+00  1.962198e+01    167400   1
      1250   5.450000e+00  4.084737e+00  1.980562e+01    168750   1
      1260   4.500000e+00  4.084737e+00  1.999886e+01    170100   1
      1261   3.437500e+00  4.084737e+00  2.002476e+01    170235   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.002476e+01
total solves   : 170235
best bound     :  4.084737e+00
simulation ci  :  4.070403e+00 ± 4.024334e-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.937500e+00  4.680797e+00  1.936049e-01      1350   1
        20   3.837500e+00  4.045414e+00  5.487151e-01      2700   1
        30   3.500000e+00  4.042649e+00  1.106626e+00      4050   1
        40   2.875000e+00  4.040373e+00  1.781107e+00      5400   1
        50   3.225000e+00  4.040120e+00  2.576815e+00      6750   1
        60   3.156250e+00  4.039310e+00  3.493933e+00      8100   1
        70   3.862500e+00  4.039108e+00  4.522533e+00      9450   1
        80   3.981250e+00  4.039016e+00  5.707046e+00     10800   1
        90   4.987500e+00  4.038885e+00  6.963831e+00     12150   1
       100   4.375000e+00  4.038892e+00  8.328899e+00     13500   1
       110   3.625000e+00  4.038822e+00  9.779048e+00     14850   1
       120   4.375000e+00  4.038812e+00  1.137747e+01     16200   1
       130   4.500000e+00  4.038779e+00  1.320195e+01     17550   1
       140   4.237500e+00  4.038772e+00  1.497758e+01     18900   1
       150   5.006250e+00  4.038769e+00  1.696172e+01     20250   1
       160   4.875000e+00  4.037585e+00  1.901503e+01     21600   1
       165   4.500000e+00  4.037575e+00  2.008074e+01     22275   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.008074e+01
total solves   : 22275
best bound     :  4.037575e+00
simulation ci  :  4.035021e+00 ± 1.189662e-01
numeric issues : 0
-------------------------------------------------------------------