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-23
-------------------------------------------------------------------
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.250000e+00  4.888859e+00  1.877499e-01      1350   1
        20   4.350000e+00  4.105855e+00  2.764089e-01      2700   1
        30   5.000000e+00  4.100490e+00  3.743489e-01      4050   1
        40   3.500000e+00  4.097376e+00  4.811618e-01      5400   1
        50   5.250000e+00  4.095859e+00  5.906360e-01      6750   1
        60   3.643750e+00  4.093342e+00  7.039089e-01      8100   1
        70   2.643750e+00  4.091818e+00  8.448479e-01      9450   1
        80   5.087500e+00  4.091591e+00  9.606690e-01     10800   1
        90   5.062500e+00  4.091309e+00  1.077343e+00     12150   1
       100   4.843750e+00  4.087004e+00  1.209099e+00     13500   1
       110   3.437500e+00  4.086094e+00  1.335766e+00     14850   1
       120   3.375000e+00  4.085926e+00  1.464710e+00     16200   1
       130   5.025000e+00  4.085866e+00  1.596310e+00     17550   1
       140   5.000000e+00  4.085734e+00  1.726706e+00     18900   1
       150   3.500000e+00  4.085655e+00  1.858942e+00     20250   1
       160   4.281250e+00  4.085454e+00  1.987671e+00     21600   1
       170   4.562500e+00  4.085425e+00  2.121325e+00     22950   1
       180   5.768750e+00  4.085425e+00  2.253372e+00     24300   1
       190   3.468750e+00  4.085359e+00  2.392332e+00     25650   1
       200   4.131250e+00  4.085225e+00  2.531488e+00     27000   1
       210   4.512500e+00  4.085157e+00  2.666052e+00     28350   1
       220   4.900000e+00  4.085153e+00  2.802269e+00     29700   1
       230   4.025000e+00  4.085134e+00  2.968379e+00     31050   1
       240   4.468750e+00  4.085116e+00  3.112222e+00     32400   1
       250   4.062500e+00  4.085075e+00  3.254012e+00     33750   1
       260   4.875000e+00  4.085037e+00  3.407897e+00     35100   1
       270   3.850000e+00  4.085011e+00  3.556714e+00     36450   1
       280   4.912500e+00  4.084992e+00  3.702490e+00     37800   1
       290   2.987500e+00  4.084986e+00  3.855415e+00     39150   1
       300   3.825000e+00  4.084957e+00  4.007635e+00     40500   1
       310   3.250000e+00  4.084911e+00  4.159536e+00     41850   1
       320   3.600000e+00  4.084896e+00  4.312353e+00     43200   1
       330   3.925000e+00  4.084896e+00  4.453149e+00     44550   1
       340   4.500000e+00  4.084893e+00  4.608159e+00     45900   1
       350   5.000000e+00  4.084891e+00  4.758861e+00     47250   1
       360   3.075000e+00  4.084866e+00  4.907562e+00     48600   1
       370   3.500000e+00  4.084861e+00  5.065237e+00     49950   1
       380   3.356250e+00  4.084857e+00  5.240539e+00     51300   1
       390   5.500000e+00  4.084846e+00  5.406595e+00     52650   1
       400   4.475000e+00  4.084846e+00  5.562415e+00     54000   1
       410   3.750000e+00  4.084843e+00  5.721962e+00     55350   1
       420   3.687500e+00  4.084843e+00  5.882730e+00     56700   1
       430   4.337500e+00  4.084825e+00  6.045985e+00     58050   1
       440   5.750000e+00  4.084825e+00  6.192657e+00     59400   1
       450   4.925000e+00  4.084792e+00  6.358198e+00     60750   1
       460   3.600000e+00  4.084792e+00  6.519021e+00     62100   1
       470   4.387500e+00  4.084792e+00  6.678993e+00     63450   1
       480   4.000000e+00  4.084792e+00  6.846490e+00     64800   1
       490   2.975000e+00  4.084788e+00  7.007731e+00     66150   1
       500   3.125000e+00  4.084788e+00  7.166980e+00     67500   1
       510   4.250000e+00  4.084788e+00  7.335267e+00     68850   1
       520   4.512500e+00  4.084786e+00  7.492054e+00     70200   1
       530   3.875000e+00  4.084786e+00  7.678692e+00     71550   1
       540   4.387500e+00  4.084781e+00  7.846354e+00     72900   1
       550   5.281250e+00  4.084780e+00  8.015610e+00     74250   1
       560   4.650000e+00  4.084780e+00  8.174294e+00     75600   1
       570   3.062500e+00  4.084780e+00  8.335514e+00     76950   1
       580   3.187500e+00  4.084780e+00  8.492017e+00     78300   1
       590   3.812500e+00  4.084780e+00  8.646025e+00     79650   1
       600   3.637500e+00  4.084774e+00  8.813586e+00     81000   1
       610   3.950000e+00  4.084765e+00  8.976802e+00     82350   1
       620   4.625000e+00  4.084760e+00  9.141105e+00     83700   1
       630   4.218750e+00  4.084760e+00  9.309526e+00     85050   1
       640   3.025000e+00  4.084755e+00  9.474966e+00     86400   1
       650   2.993750e+00  4.084751e+00  9.635451e+00     87750   1
       660   3.262500e+00  4.084746e+00  9.798787e+00     89100   1
       670   3.625000e+00  4.084746e+00  9.983575e+00     90450   1
       680   2.981250e+00  4.084746e+00  1.015165e+01     91800   1
       690   4.187500e+00  4.084746e+00  1.031641e+01     93150   1
       700   4.500000e+00  4.084746e+00  1.047690e+01     94500   1
       710   3.225000e+00  4.084746e+00  1.064368e+01     95850   1
       720   4.375000e+00  4.084746e+00  1.081499e+01     97200   1
       730   2.650000e+00  4.084746e+00  1.098676e+01     98550   1
       740   3.250000e+00  4.084746e+00  1.115157e+01     99900   1
       750   4.725000e+00  4.084746e+00  1.133061e+01    101250   1
       760   3.375000e+00  4.084746e+00  1.150819e+01    102600   1
       770   5.375000e+00  4.084746e+00  1.168137e+01    103950   1
       780   4.068750e+00  4.084746e+00  1.185988e+01    105300   1
       790   4.412500e+00  4.084746e+00  1.204015e+01    106650   1
       800   4.350000e+00  4.084746e+00  1.221823e+01    108000   1
       810   5.887500e+00  4.084746e+00  1.241617e+01    109350   1
       820   4.912500e+00  4.084746e+00  1.258831e+01    110700   1
       830   4.387500e+00  4.084746e+00  1.275505e+01    112050   1
       840   3.675000e+00  4.084746e+00  1.293149e+01    113400   1
       850   5.375000e+00  4.084746e+00  1.310359e+01    114750   1
       860   3.562500e+00  4.084746e+00  1.328590e+01    116100   1
       870   3.075000e+00  4.084746e+00  1.346884e+01    117450   1
       880   3.625000e+00  4.084746e+00  1.364413e+01    118800   1
       890   2.937500e+00  4.084746e+00  1.382023e+01    120150   1
       900   4.450000e+00  4.084746e+00  1.400014e+01    121500   1
       910   4.200000e+00  4.084746e+00  1.417700e+01    122850   1
       920   3.687500e+00  4.084746e+00  1.436103e+01    124200   1
       930   4.725000e+00  4.084746e+00  1.454133e+01    125550   1
       940   4.018750e+00  4.084746e+00  1.471392e+01    126900   1
       950   4.675000e+00  4.084746e+00  1.490718e+01    128250   1
       960   3.375000e+00  4.084746e+00  1.507669e+01    129600   1
       970   3.812500e+00  4.084746e+00  1.524586e+01    130950   1
       980   3.112500e+00  4.084746e+00  1.542035e+01    132300   1
       990   3.600000e+00  4.084746e+00  1.559676e+01    133650   1
      1000   5.500000e+00  4.084746e+00  1.577723e+01    135000   1
      1010   3.187500e+00  4.084746e+00  1.595453e+01    136350   1
      1020   4.900000e+00  4.084746e+00  1.613224e+01    137700   1
      1030   3.637500e+00  4.084746e+00  1.632320e+01    139050   1
      1040   3.975000e+00  4.084746e+00  1.650110e+01    140400   1
      1050   4.750000e+00  4.084746e+00  1.668406e+01    141750   1
      1060   4.437500e+00  4.084746e+00  1.688250e+01    143100   1
      1070   5.000000e+00  4.084746e+00  1.707002e+01    144450   1
      1080   4.143750e+00  4.084746e+00  1.727600e+01    145800   1
      1090   5.625000e+00  4.084746e+00  1.745332e+01    147150   1
      1100   3.475000e+00  4.084746e+00  1.764022e+01    148500   1
      1110   4.156250e+00  4.084746e+00  1.783167e+01    149850   1
      1120   4.450000e+00  4.084746e+00  1.802015e+01    151200   1
      1130   3.312500e+00  4.084741e+00  1.821387e+01    152550   1
      1140   5.375000e+00  4.084741e+00  1.839694e+01    153900   1
      1150   4.800000e+00  4.084737e+00  1.859245e+01    155250   1
      1160   3.300000e+00  4.084737e+00  1.878005e+01    156600   1
      1170   4.356250e+00  4.084737e+00  1.896789e+01    157950   1
      1180   3.900000e+00  4.084737e+00  1.916082e+01    159300   1
      1190   4.450000e+00  4.084737e+00  1.935701e+01    160650   1
      1200   5.156250e+00  4.084737e+00  1.955350e+01    162000   1
      1210   4.500000e+00  4.084737e+00  1.975640e+01    163350   1
      1220   4.875000e+00  4.084737e+00  1.995993e+01    164700   1
      1222   4.562500e+00  4.084737e+00  2.001116e+01    164970   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.001116e+01
total solves   : 164970
best bound     :  4.084737e+00
simulation ci  :  4.071580e+00 ± 4.071235e-02
numeric issues : 0
-------------------------------------------------------------------

-------------------------------------------------------------------
         SDDP.jl (c) Oscar Dowson and contributors, 2017-23
-------------------------------------------------------------------
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.925000e+00  6.001820e+00  2.001181e-01      1350   1
        20   4.056250e+00  5.577813e+00  5.905550e-01      2700   1
        30   3.000000e+00  4.731415e+00  1.055519e+00      4050   1
        40   5.025000e+00  4.043470e+00  1.598490e+00      5400   1
        50   4.250000e+00  4.039874e+00  2.228620e+00      6750   1
        60   4.312500e+00  4.039177e+00  2.997896e+00      8100   1
        70   4.525000e+00  4.039054e+00  3.947202e+00      9450   1
        80   3.687500e+00  4.039051e+00  4.996612e+00     10800   1
        90   2.987500e+00  4.038970e+00  6.174462e+00     12150   1
       100   3.225000e+00  4.038843e+00  7.470227e+00     13500   1
       110   4.500000e+00  4.038843e+00  8.833097e+00     14850   1
       120   5.750000e+00  4.038813e+00  1.035241e+01     16200   1
       130   3.700000e+00  4.038777e+00  1.193610e+01     17550   1
       140   3.800000e+00  4.038777e+00  1.361731e+01     18900   1
       150   2.687500e+00  4.038777e+00  1.537175e+01     20250   1
       160   4.737500e+00  4.038777e+00  1.736846e+01     21600   1
       170   4.550000e+00  4.038777e+00  1.948146e+01     22950   1
       173   3.975000e+00  4.038777e+00  2.003830e+01     23355   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.003830e+01
total solves   : 23355
best bound     :  4.038777e+00
simulation ci  :  4.084772e+00 ± 1.131171e-01
numeric issues : 0
-------------------------------------------------------------------