Deterministic 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 all_blacks()
    # Number of time periods, number of seats, R_ij = revenue from selling seat
    # i at time j, offer_ij = whether an offer for seat i will come at time j
    (T, N, R, offer) = (3, 2, [3 3 6; 3 3 6], [1 1 0; 1 0 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
        @variable(sp, accept_offer, Bin)
        # Balance on seats
        @constraint(
            sp,
            [i in 1:N],
            x[i].out == x[i].in - offer[i, stage] * accept_offer
        )
        @stageobjective(
            sp,
            sum(R[i, stage] * offer[i, stage] * accept_offer for i in 1:N)
        )
    end
    SDDP.train(model; duality_handler = SDDP.LagrangianDuality())
    @test SDDP.calculate_bound(model) ≈ 9.0
    return
end

all_blacks()

-------------------------------------------------------------------
         SDDP.jl (c) Oscar Dowson and contributors, 2017-23
-------------------------------------------------------------------
problem
  nodes           : 3
  state variables : 2
  scenarios       : 1.00000e+00
  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}         : [2, 2]
  VariableRef in MOI.GreaterThan{Float64} : [2, 3]
  VariableRef in MOI.LessThan{Float64}    : [3, 3]
  VariableRef in MOI.ZeroOne              : [3, 3]
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  9.000000e+00  4.185200e-02         6   1
        20L  9.000000e+00  9.000000e+00  1.023970e-01       123   1
-------------------------------------------------------------------
status         : simulation_stopping
total time (s) : 1.023970e-01
total solves   : 123
best bound     :  9.000000e+00
simulation ci  :  8.850000e+00 ± 2.940000e-01
numeric issues : 0
-------------------------------------------------------------------