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.414815e+01 3.749490e-02 11 1
40L 6.000000e+00 8.000000e+00 4.160261e-01 602 1
-------------------------------------------------------------------
status : simulation_stopping
total time (s) : 4.160261e-01
total solves : 602
best bound : 8.000000e+00
simulation ci : 7.125000e+00 ± 8.068707e-01
numeric issues : 0
-------------------------------------------------------------------