Stochastic All Blacks

This tutorial was generated using Literate.jl. Download the source as a .jl file. Download the source as a .ipynb file.

using SDDP, HiGHS, Test

function stochastic_all_blacks()
    # Number of time periods
    T = 3
    # Number of seats
    N = 2
    # R_ij = price of seat i at time j
    R = [3 3 6; 3 3 6]
    # Number of noises
    s = 3
    offers = [
        [[1, 1], [0, 0], [1, 1]],
        [[1, 0], [0, 0], [0, 0]],
        [[0, 1], [1, 0], [1, 1]],
    ]

    model = SDDP.LinearPolicyGraph(;
        stages = T,
        sense = :Max,
        upper_bound = 100.0,
        optimizer = HiGHS.Optimizer,
    ) do sp, stage
        # Seat remaining?
        @variable(sp, 0 <= x[1:N] <= 1, SDDP.State, Bin, initial_value = 1)
        # Action: accept offer, or don't accept offer
        # We are allowed to accept some of the seats offered but not others
        @variable(sp, accept_offer[1:N], Bin)
        @variable(sp, offers_made[1:N])
        # Balance on seats
        @constraint(
            sp,
            balance[i in 1:N],
            x[i].in - x[i].out == accept_offer[i]
        )
        @stageobjective(sp, sum(R[i, stage] * accept_offer[i] for i in 1:N))
        SDDP.parameterize(sp, offers[stage]) do o
            return JuMP.fix.(offers_made, o)
        end
        @constraint(sp, accept_offer .<= offers_made)
    end

    SDDP.train(model; duality_handler = SDDP.LagrangianDuality())
    @test SDDP.calculate_bound(model) ≈ 8.0
    return
end

stochastic_all_blacks()

-------------------------------------------------------------------
         SDDP.jl (c) Oscar Dowson and contributors, 2017-24
-------------------------------------------------------------------
problem
  nodes           : 3
  state variables : 2
  scenarios       : 2.70000e+01
  existing cuts   : false
options
  solver          : serial mode
  risk measure    : SDDP.Expectation()
  sampling scheme : SDDP.InSampleMonteCarlo
subproblem structure
  VariableRef                             : [9, 9]
  AffExpr in MOI.EqualTo{Float64}         : [2, 2]
  AffExpr in MOI.LessThan{Float64}        : [2, 2]
  VariableRef in MOI.GreaterThan{Float64} : [2, 3]
  VariableRef in MOI.LessThan{Float64}    : [3, 3]
  VariableRef in MOI.ZeroOne              : [4, 4]
numerical stability report
  matrix range     [1e+00, 1e+00]
  objective range  [1e+00, 6e+00]
  bounds range     [1e+00, 1e+02]
  rhs range        [0e+00, 0e+00]
-------------------------------------------------------------------
 iteration    simulation      bound        time (s)     solves  pid
-------------------------------------------------------------------
         1L  6.000000e+00  1.200000e+01  4.694200e-02        11   1
        40L  6.000000e+00  8.000000e+00  4.237339e-01       602   1
-------------------------------------------------------------------
status         : simulation_stopping
total time (s) : 4.237339e-01
total solves   : 602
best bound     :  8.000000e+00
simulation ci  :  7.125000e+00 ± 6.882847e-01
numeric issues : 0
-------------------------------------------------------------------