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-24
-------------------------------------------------------------------
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 3.453207e-02 6 1
20L 9.000000e+00 9.000000e+00 7.483411e-02 123 1
-------------------------------------------------------------------
status : simulation_stopping
total time (s) : 7.483411e-02
total solves : 123
best bound : 9.000000e+00
simulation ci : 8.850000e+00 ± 2.940000e-01
numeric issues : 0
-------------------------------------------------------------------