SDDP with Quasi Monte Carlo sampling

FelixSchmidt · April 1, 2024, 8:03am

Hi Oscar (@odow),
I am working on a SDDP implementation of a capacity expansion problem using SDDP.jl. I suspect that convergence could be improved by using a type of stratified sampling scheme in the forward pass, such as Latin Hypercube Sampling. I saw that you discussed such methods, at least for the upper bound simulations, in your thesis. It does not seem straightforward to implement a QMC sampling scheme in SDDP.jl, especially in the parallel setup, since draws of different parallel passes would depend on each other. Have you or anyone else ever done this in SDDP.jl? Would you have any pointers on what to bear in mind?

Thank you very much,

Felix

odow · April 1, 2024, 9:16pm

Hi @FelixSchmidt,

I implemented something like LHS at one point in a very old version of SDDP.jl, but it doesn’t exist in the current version.

The approach would be to define a new AbstractSamplingScheme:

github.com

odow/SDDP.jl/blob/master/src/plugins/sampling_schemes.jl

#  Copyright (c) 2017-23, Oscar Dowson and SDDP.jl contributors.
#  This Source Code Form is subject to the terms of the Mozilla Public
#  License, v. 2.0. If a copy of the MPL was not distributed with this
#  file, You can obtain one at http://mozilla.org/MPL/2.0/.

# ========================= Monte Carlo Sampling Scheme ====================== #

struct InSampleMonteCarlo <: AbstractSamplingScheme
    max_depth::Int
    terminate_on_cycle::Bool
    terminate_on_dummy_leaf::Bool
    rollout_limit::Function
    initial_node::Any
end

"""
    InSampleMonteCarlo(;
        max_depth::Int = 0,
        terminate_on_cycle::Function = false,
        terminate_on_dummy_leaf::Function = true,

This file has been truncated. show original

That you could call via SDDP.train(model; sampling_scheme = LHSSamplingScheme()).

For the parallel passes, you’d likely need to initialize the scheme with a different starting point on each thread, or just ignore that for now.

FelixSchmidt · April 2, 2024, 9:03am

Hi Oscar,

thank you very much! I will give this a try!

Best
Felix