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.888669e+00  1.648998e-01      1350   1
        20   4.350000e+00  4.105556e+00  2.509530e-01      2700   1
        30   5.000000e+00  4.099889e+00  3.487120e-01      4050   1
        40   3.500000e+00  4.096596e+00  4.545598e-01      5400   1
        50   5.250000e+00  4.095112e+00  5.657809e-01      6750   1
        60   3.643750e+00  4.092827e+00  6.840398e-01      8100   1
        70   2.643750e+00  4.091514e+00  7.981379e-01      9450   1
        80   5.087500e+00  4.091301e+00  9.148009e-01     10800   1
        90   5.062500e+00  4.090986e+00  1.030168e+00     12150   1
       100   4.843750e+00  4.086917e+00  1.160880e+00     13500   1
       110   3.400000e+00  4.085985e+00  1.286889e+00     14850   1
       120   3.375000e+00  4.085819e+00  1.414850e+00     16200   1
       130   5.025000e+00  4.085765e+00  1.547287e+00     17550   1
       140   5.000000e+00  4.085640e+00  1.675500e+00     18900   1
       150   3.500000e+00  4.085560e+00  1.803753e+00     20250   1
       160   4.281250e+00  4.085411e+00  1.955412e+00     21600   1
       170   4.562500e+00  4.085379e+00  2.087663e+00     22950   1
       180   5.768750e+00  4.085379e+00  2.217077e+00     24300   1
       190   3.468750e+00  4.085337e+00  2.352901e+00     25650   1
       200   4.131250e+00  4.085202e+00  2.488050e+00     27000   1
       210   4.512500e+00  4.085132e+00  2.631313e+00     28350   1
       220   4.900000e+00  4.085130e+00  2.767367e+00     29700   1
       230   4.025000e+00  4.085111e+00  2.902879e+00     31050   1
       240   4.468750e+00  4.085094e+00  3.044212e+00     32400   1
       250   4.062500e+00  4.085056e+00  3.182452e+00     33750   1
       260   4.875000e+00  4.085019e+00  3.328798e+00     35100   1
       270   3.850000e+00  4.084990e+00  3.470359e+00     36450   1
       280   4.912500e+00  4.084971e+00  3.611864e+00     37800   1
       290   2.987500e+00  4.084965e+00  3.759992e+00     39150   1
       300   3.825000e+00  4.084940e+00  3.913076e+00     40500   1
       310   3.250000e+00  4.084900e+00  4.065368e+00     41850   1
       320   3.537500e+00  4.084889e+00  4.213393e+00     43200   1
       330   3.950000e+00  4.084889e+00  4.379249e+00     44550   1
       340   4.500000e+00  4.084886e+00  4.524798e+00     45900   1
       350   5.000000e+00  4.084886e+00  4.667817e+00     47250   1
       360   3.075000e+00  4.084864e+00  4.813132e+00     48600   1
       370   3.500000e+00  4.084859e+00  4.966779e+00     49950   1
       380   3.356250e+00  4.084854e+00  5.120142e+00     51300   1
       390   5.500000e+00  4.084839e+00  5.275948e+00     52650   1
       400   4.475000e+00  4.084834e+00  5.422108e+00     54000   1
       410   3.750000e+00  4.084832e+00  5.570609e+00     55350   1
       420   3.687500e+00  4.084832e+00  5.724658e+00     56700   1
       430   4.337500e+00  4.084811e+00  5.882289e+00     58050   1
       440   5.750000e+00  4.084811e+00  6.022937e+00     59400   1
       450   4.937500e+00  4.084776e+00  6.183115e+00     60750   1
       460   3.600000e+00  4.084776e+00  6.341070e+00     62100   1
       470   4.387500e+00  4.084776e+00  6.488384e+00     63450   1
       480   4.000000e+00  4.084771e+00  6.646559e+00     64800   1
       490   2.975000e+00  4.084769e+00  6.809901e+00     66150   1
       500   3.125000e+00  4.084769e+00  6.986242e+00     67500   1
       510   4.250000e+00  4.084769e+00  7.158323e+00     68850   1
       520   4.525000e+00  4.084767e+00  7.313242e+00     70200   1
       530   3.875000e+00  4.084767e+00  7.487013e+00     71550   1
       540   4.387500e+00  4.084762e+00  7.660255e+00     72900   1
       550   5.287500e+00  4.084762e+00  7.838036e+00     74250   1
       560   4.650000e+00  4.084762e+00  7.994974e+00     75600   1
       570   3.062500e+00  4.084762e+00  8.161216e+00     76950   1
       580   3.187500e+00  4.084758e+00  8.325656e+00     78300   1
       590   3.812500e+00  4.084758e+00  8.478542e+00     79650   1
       600   3.637500e+00  4.084746e+00  8.639452e+00     81000   1
       610   3.925000e+00  4.084746e+00  8.802190e+00     82350   1
       620   4.625000e+00  4.084746e+00  8.967913e+00     83700   1
       630   4.218750e+00  4.084746e+00  9.134595e+00     85050   1
       640   3.025000e+00  4.084746e+00  9.306375e+00     86400   1
       650   2.993750e+00  4.084746e+00  9.463239e+00     87750   1
       660   3.262500e+00  4.084746e+00  9.645423e+00     89100   1
       670   3.575000e+00  4.084746e+00  9.817763e+00     90450   1
       680   2.981250e+00  4.084746e+00  9.985817e+00     91800   1
       690   4.187500e+00  4.084746e+00  1.015689e+01     93150   1
       700   4.500000e+00  4.084746e+00  1.032539e+01     94500   1
       710   3.225000e+00  4.084746e+00  1.049425e+01     95850   1
       720   4.375000e+00  4.084746e+00  1.067993e+01     97200   1
       730   2.650000e+00  4.084746e+00  1.085818e+01     98550   1
       740   3.250000e+00  4.084746e+00  1.104094e+01     99900   1
       750   4.725000e+00  4.084746e+00  1.123251e+01    101250   1
       760   3.375000e+00  4.084746e+00  1.142026e+01    102600   1
       770   5.375000e+00  4.084746e+00  1.160450e+01    103950   1
       780   4.068750e+00  4.084746e+00  1.178450e+01    105300   1
       790   4.412500e+00  4.084746e+00  1.198229e+01    106650   1
       800   4.350000e+00  4.084746e+00  1.216782e+01    108000   1
       810   5.900000e+00  4.084746e+00  1.236381e+01    109350   1
       820   4.912500e+00  4.084746e+00  1.257733e+01    110700   1
       830   4.387500e+00  4.084746e+00  1.275904e+01    112050   1
       840   3.712500e+00  4.084746e+00  1.294703e+01    113400   1
       850   5.375000e+00  4.084746e+00  1.312981e+01    114750   1
       860   3.562500e+00  4.084746e+00  1.333230e+01    116100   1
       870   3.075000e+00  4.084746e+00  1.352700e+01    117450   1
       880   3.625000e+00  4.084746e+00  1.371528e+01    118800   1
       890   2.937500e+00  4.084746e+00  1.389716e+01    120150   1
       900   4.450000e+00  4.084746e+00  1.408592e+01    121500   1
       910   4.200000e+00  4.084746e+00  1.429070e+01    122850   1
       920   3.687500e+00  4.084746e+00  1.449292e+01    124200   1
       930   4.687500e+00  4.084746e+00  1.467831e+01    125550   1
       940   4.018750e+00  4.084746e+00  1.486387e+01    126900   1
       950   4.625000e+00  4.084746e+00  1.504508e+01    128250   1
       960   3.375000e+00  4.084746e+00  1.522294e+01    129600   1
       970   3.812500e+00  4.084746e+00  1.541984e+01    130950   1
       980   3.112500e+00  4.084746e+00  1.560230e+01    132300   1
       990   3.600000e+00  4.084746e+00  1.579720e+01    133650   1
      1000   5.500000e+00  4.084746e+00  1.598597e+01    135000   1
      1010   3.187500e+00  4.084746e+00  1.618315e+01    136350   1
      1020   4.900000e+00  4.084746e+00  1.637049e+01    137700   1
      1030   3.637500e+00  4.084746e+00  1.658073e+01    139050   1
      1040   3.975000e+00  4.084746e+00  1.676955e+01    140400   1
      1050   4.750000e+00  4.084746e+00  1.696201e+01    141750   1
      1060   4.437500e+00  4.084746e+00  1.717360e+01    143100   1
      1070   5.000000e+00  4.084746e+00  1.736055e+01    144450   1
      1080   4.143750e+00  4.084746e+00  1.756261e+01    145800   1
      1090   5.625000e+00  4.084746e+00  1.775128e+01    147150   1
      1100   3.475000e+00  4.084746e+00  1.793851e+01    148500   1
      1110   4.156250e+00  4.084746e+00  1.813441e+01    149850   1
      1120   4.450000e+00  4.084746e+00  1.835230e+01    151200   1
      1130   3.225000e+00  4.084741e+00  1.854592e+01    152550   1
      1140   5.375000e+00  4.084741e+00  1.872128e+01    153900   1
      1150   4.800000e+00  4.084737e+00  1.891283e+01    155250   1
      1160   3.300000e+00  4.084737e+00  1.909349e+01    156600   1
      1170   4.356250e+00  4.084737e+00  1.928687e+01    157950   1
      1180   3.900000e+00  4.084737e+00  1.948563e+01    159300   1
      1190   4.450000e+00  4.084737e+00  1.967977e+01    160650   1
      1200   5.156250e+00  4.084737e+00  1.987337e+01    162000   1
      1207   4.750000e+00  4.084737e+00  2.001382e+01    162945   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.001382e+01
total solves   : 162945
best bound     :  4.084737e+00
simulation ci  :  4.068465e+00 ± 4.099361e-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.800000e+00  4.409619e+00  1.790011e-01      1350   1
        20   5.250000e+00  4.399397e+00  5.437090e-01      2700   1
        30   4.125000e+00  4.336935e+00  1.048731e+00      4050   1
        40   2.550000e+00  4.047548e+00  1.669310e+00      5400   1
        50   3.637500e+00  4.042638e+00  2.382298e+00      6750   1
        60   3.875000e+00  4.040121e+00  3.108443e+00      8100   1
        70   2.981250e+00  4.039179e+00  4.010416e+00      9450   1
        80   4.125000e+00  4.039034e+00  5.039032e+00     10800   1
        90   4.875000e+00  4.038962e+00  6.261034e+00     12150   1
       100   4.275000e+00  4.038879e+00  7.517578e+00     13500   1
       110   4.843750e+00  4.038879e+00  8.929122e+00     14850   1
       120   5.625000e+00  4.038825e+00  1.041227e+01     16200   1
       130   4.375000e+00  4.038808e+00  1.207345e+01     17550   1
       140   4.962500e+00  4.038801e+00  1.373721e+01     18900   1
       150   2.893750e+00  4.038777e+00  1.559038e+01     20250   1
       160   5.287500e+00  4.038777e+00  1.757976e+01     21600   1
       170   4.250000e+00  4.038770e+00  1.966844e+01     22950   1
       172   4.037500e+00  4.038770e+00  2.010557e+01     23220   1
-------------------------------------------------------------------
status         : time_limit
total time (s) : 2.010557e+01
total solves   : 23220
best bound     :  4.038770e+00
simulation ci  :  4.097582e+00 ± 1.128328e-01
numeric issues : 0
-------------------------------------------------------------------