Decision-Hazard variables

[odow]

So, it would be nice to be able to solve decision-hazard problem. Ideally, the syntax would look like this:

# State variables: just the usual.
@variable(sp, x, SDDP.State(), initial_value = 0)
# Non-anticipative variables: these are the 'decision' in DH.
@variable(sp, u, SDDP.Nonanticipative())
# A recourse/anticipative variable: this is needed because some 
# modeling variables might need to vary based on the noise.
@variable(sp, v)
# A constraint that mixes state variables, non-anticipative variables, 
# and normal variables.
@constraint(sp, x.out == x.in - u + v)
# Here is the parameterization. We can't use non-anticipative 
# variables in here.
SDDP.parameterize(sp, [1, 2]) do w
    JuMP.fix(v, w)
end

cc @Thuener

[Thuener]

Yes. I would like to help you with this but I'm afraid I can't easily navigate through the framework.

[odow]

I don't have a good way to do this. Ideally, the easiest way is to expand the state-space, but then we may need to add additional nodes to the policy graph. Another complication is respecting constraints that might appear in the hazard part of the decision part.

The alternative is solving each node as the two-stage stochastic program. But that adds complexity.

[juyoungwang]

Hi @odow,

Regarding SDPP.jl package, it seems like Thuener has "SDDP.Nonanticipative()" in his code. I tried to find this command to use it for my code, and it seems like that for the version of SDDP.jl (0.1) that I'm using, such configuration is not available (I'm not sure, but I could not find .Nonanticipative() for by doing SDDP. + Tap button).

Can you please let me know how to deal with this issue?

Each time I simulate (e.g. 10 times), I'm getting different first stage solution value for each simulation...

[odow]

Hi @jyw1189, this is an open issue because it isn't implemented yet.

For now, the only way to formulate decision-hazard problems is through the state-space expansion trick. For more on this, see http://www.optimization-online.org/DB_HTML/2018/10/6855.html.

You should also take a look at Section 2.3 and Figure 3 in http://www.optimization-online.org/DB_HTML/2018/11/6914.html.

[juyoungwang]

Thanks a lot !

[odow]

Let me know if you need help implementing anything. I don't think there are many (any) examples or documentation, so that would be good to add.

[juyoungwang]

Okay. Thanks a lot for being so supportive :)

[odow]

Plan

Add SDDP.Nonanticipative as a variable extension

@variable(model, 0 <= u[1:4] <= 10, Integer, SDDP.Nonanticipative) 

This should work for all JuMP variables, including binary and integer variables. But you should not be able to write

@variable(model, 0 <= x[1:4] <= 10, SDDP.State, SDDP.Nonanticipative) 

Then, inside a node with SDDP.Nonanticipative variables, add a "hidden" node with the state expansion. It should just contain the existing states, and transform the nonanticipative variables into state variables. The stage objective should be 0.0. Existing states should be mapped through such that x.out = x.in.

Bounds on the nonanticipative controls should be moved to the hidden node. Then, in the proper node we should add extra state variables and force new_control.in = u.

Risk

The risk measure should also be moved to the hidden node.

Feasibility

I think this is going to require us to add feasibility cuts to the hidden node for the controls.

I have resisted added feasibility cuts in general, because that will allow people to write models without relatively complete recourse, and I don't want that to happen. The alternative is asking people to write models with relatively complete recourse for the controls, but that is probably too hard to explain/tedious to implement because it will require a lot of penalty terms.

Parent nodes

Parent nodes should only "see" the hidden decision node.

Belief states

How to handle belief states?

Alternatives

Transform the subproblem into a two-stage stochastic program and solve the deterministic equivalent. Issues: requires multi-cut, along with a duplication of the state variables so that each set of cuts have their own copy of the state variables.

Pros: potentially faster. Cons: harder to integrate into the library. Not obvious how to leverage existing risk measures. Also objective and belief states get confusing.

BKP has a group implementing this. Will be interesting as a comparison.

[odow]

Closing for now because I don't know an easy way to do this, or how desired it is. If you stumble upon this issue and want this functionality, please leave a comment. I will re-open if there are enough people interested.

[anll4175]

How can we implement variables, which are not scenario dependent (here and now variables) ?

[odow]

You need to make it a state variable that is chosen in the previous stage. Please open a new issue with a reproducible example if you are having trouble.

See Figure 3 of https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21932

[anll4175]

10 decision variables, which are not scenario dependent 7 decision variables are scenario dependent

Should I make 10 state variables ? Working on my Julia code (not using SDDP package). I created two nodes ( one for decision-hazard variables, other one for hazard-decision variables) but not complicated. You mentioned about hidden notes, note clear application of state variable and hidden note,

[odow]

Does this help?

using SDDP, GLPK
model = SDDP.LinearPolicyGraph(
    stages = 4,
    sense = :Max,
    upper_bound = 1e4,
    optimizer = GLPK.Optimizer,
) do sp, t
    # A state variable.
    @variable(sp, x >= 0, SDDP.State, initial_value = 0.0)
    # In stage t, next_buy.in is a scenario-independent (decision-hazard) 
    # control that was chosen as next_buy.out in stage t-1.
    @variable(sp, next_buy >= 0, SDDP.State, initial_value = 0.0)
    # A scenario-dependent (hazard-decision) control variable.
    @variable(sp, sell >= 0)
    # The widgets in inventory at the end of the period is how much we had at
    # the start, plus our scenario-independent purchasing decision, less our 
    # scenario-dependent sales decision.
    @constraint(sp, x.out == x.in + next_buy.in - sell)
    # We profit by selling goods, and we incur the cost of buying them now.
    @stageobjective(sp, 1.2 * sell - next_buy.out)
    # Can't sell more than demand.
    SDDP.parameterize(sp, [1, 2, 3]) do demand
        set_upper_bound(sell, demand)
    end
end

You don't need to make two explicit nodes. You can combine them. This paper also explains what to do: https://www.sciencedirect.com/science/article/abs/pii/S0306261920313969