User question: stochastic lead times

[slwu89]

Hi,

I'm trying to figure out how to adapt the example in the docs here: https://odow.github.io/SDDP.jl/stable/guides/access_previous_variables/#Access-a-decision-from-N-stages-ago to the situation where the lead time is variable, which is important for modeling my problem. I am not sure what's the best way to go about it, I tried with the code below, which also implements a "conveyor belt" style of advancement from a lead time at pipeline[i] to the "ready to go" point at pipeline[1]. In this example I consider the lead time to follow a truncated Geometric distribution, but because I can't use one JuMP variable to subset another, I'm unsure what is a good alternative. I'm pasting what I have below (i.e. what I wish I could run). Does anyone have any suggestions? Thanks!

I'm on SDDP v1.1.4.

using SDDP, JuMP, HiGHS
using Random, Distributions
max_delay = 50
geom_p = 1/5
probs = pdf.(Geometric(geom_p), 0:max_delay-1)
probs .= probs / sum(probs)
support = collect(1:max_delay)

model = SDDP.LinearPolicyGraph(
    stages = 20,
    sense = :Max,
    upper_bound = 100,
    optimizer = HiGHS.Optimizer
) do sp, t
    # Current inventory on hand.
    @variable(sp, inventory >= 0, SDDP.State, initial_value = 0)

    # Inventory pipeline.
    @variable(sp, pipeline[1:max_delay], SDDP.State, initial_value = 0)

    # The number of units to order today.
    @variable(sp, 0 <= buy <= 10)

    # The number of units to sell today.
    @variable(sp, sell >= 0)

    # delay in shipping
    @variable(sp, delay)

    # delay for this order (shipping+production)
    SDDP.parameterize(sp, support, probs) do ω
        return JuMP.fix(delay, ω)
    end
    # Buy orders get placed in the pipeline.
    @constraint(sp, pipeline[delay].out == buy)

    # orders moves up one slot in the pipeline each stage.
    @constraint(sp, [i=1:max_delay-1], pipeline[i].out == pipeline[i+1].in)

    # Stock balance constraint.
    @constraint(sp, inventory.out == inventory.in - sell + pipeline[1].in)

    # Maximize quantity of sold items.
    @stageobjective(sp, sell)
end

[odow]

I'd use this trick:

using SDDP
import HiGHS
import Distributions
T = 10
model = SDDP.LinearPolicyGraph(
    stages = 20,
    sense = :Max,
    upper_bound = 1000,
    optimizer = HiGHS.Optimizer,
) do sp, t
    @variables(sp, begin
        x_inventory >= 0, SDDP.State, (initial_value = 0)
        x_orders[1:T+1], SDDP.State, (initial_value = 0)
        0 <= u_buy <= 10
        u_sell >= 0
    end)
    fix(x_orders[T+1].out, 0)
    @stageobjective(sp, u_sell)
    @constraints(sp, begin
        c_orders[i=1:T], x_orders[i+1].in + 1 * u_buy == x_orders[i].out
        x_inventory.out == x_inventory.in - u_sell + x_orders[1].in
    end)
    Ω = 1:T
    P = Distributions.pdf.(Distributions.Geometric(1 / 5), 0:T-1)
    P ./= sum(P)
    SDDP.parameterize(sp, Ω, P) do ω
        # Rewrite the constraint c_orders[i=1:T] to
        #   x_orders[i+1].in + 1 * u_buy == x_orders[i].out
        # if ω == i and
        #   x_orders[i+1].in + 0 * u_buy == x_orders[i].out
        # if ω != i.
        for i in Ω
            set_normalized_coefficient(c_orders[i], u_buy, ω == i ? 1 : 0)
        end
    end
end
SDDP.train(model; iteration_limit = 10)

[slwu89]

Very slick! Thank you @odow, I didn't know about the set_normalized_coefficient from JuMP. I see that the c_orders constraints now handle both moving orders up in the pipeline and placing the new order in the right place.

[odow]

I didn't know about the set_normalized_coefficient from JuMP

See https://odow.github.io/SDDP.jl/stable/guides/add_noise_in_the_constraint_matrix.

But yeah. One problem with SDDP.jl is that there's a bit of art in knowing how to represent something, and it isn't always obvious to new users. And it's hard to teach because each situation is subtly different.

[slwu89]

Indeed, thanks for taking the time to show me this.

[odow]

Closing because this seems resolved. Please re-open if you have further questions

[Thuener]

Very nice trick @odow! I suggest adding to https://sddp.dev/stable/guides/access_previous_variables/. I can make the PR.

[odow]

PRs accepted :smile: