I have an optimization problem where one of the constraints is a convex non-linear constraint on the following form:
Here w, eta and x are decision variables. All variables with an m index are variables corresponding to the parent node in t = t-1, while all variables and parameters indexed with an n corresponds to the node you are in at t = t. According to my understanding, the w variables can be created as state variables, but I am a little bit unsure if it is possible to formulate the last part of the constraint using the SDDP package. To formulate this part of the constraint, you will need to access all eta variables which are children of the node you are standing in at t = t, square them and multiply them by the probability of going from the current node n to the node v in t = t+1 (p_nv).
My attempt to formulate the first part of the constraint is the following: @constraint(subproblem, B[time] * (w.in - w.out) + eta + P[time][node] - A * () >= 0)
I hope someone knows a way to solve this problem or alternatively other ways the problem can be solved. The underlying problem is a big hydropower problem, modelled as a lattice, which is impossible to solve to optimality, hence the usage of the SDDP package.
I don’t think you can easily formulate this problem with SDDP.jl. It doesn’t support chance constraints.
What is the interpretation of the constraint? Why is it necessary?
If you were to formulate it, you would need to add \eta_v as a state variable, and then you must decide the value of \eta_v in node n. But SDDP.jl isn’t really designed to handle this case because it requires the state dimension to be constant across nodes, so you’ll probably run into a bunch of issues.
Ok, thanks! Unfortunately the constraint is necessary, as it is part of determining the lower bound on the value of a hydropower operation using the Good Deal measure. Do you know of any other packages which may be able to solve the problem? Please note that the problem is rather large; a scenario lattice with 78 time steps and 8x8 nodes in each time step, so it will most likely need to be approximated in a similar manner to SDDP.
I have a conceptual dislike for chance constraints like this because what do you do if the future is not one of your N set? You could choose any value but if you knew about it previously, that value might make the constraint infeasible.
Since our problem is defined for an incomplete market, the eta represents the unhedged part of our production, i.e. the error in our replicating portfolio stemming from the fact that inflow is a non-financial risk factor. The term in the constraint above is specifically meant to represent the replication error computed over all successor nodes of the current node.
This formulation is well established in the current literature on Good Deal price bounds, and can be seen in for instance “Modeling Gas Markets with Endogenous Long-Term Contracts” by Abada et al.
This formulation is well established in the current literature on Good Deal price bounds
Do people use this formulation in large multistage stochastic programs that they solve with SDDP? How do they normally solve such problems?
Now you can formulate this by adding \eta as a state variable, with something like (very rough, but I hope you get the idea):
@variable(sp, eta[n in nodes[time+1]], SDDP.State)
soc_function = [
(B[time] * (w.in - w.out) + eta.in[node] + P[time][node]) / A;
[sqrt(p[node, n]) * eta[n].out for n in nodes[time+1]]
]
@constraint(sp, soc_function in SecondOrderCone())
But this requires having the same set \cal N at each node, and it requires choosing the set \eta_v for all possible v at node n. Couple that with the SOC constraint, and I don’t think this will solve very well, if at all. Particularly when you have a large number of stages and realizations.
I don’t belive the current literature solves it with SDDP, typically the literature concerns much smaller problems so they may not require an approximation. In regards to your statement “But this requires having the same set N at each node”, since the problem is modeled as a lattice this should not be a problem right? All nodes in a time step go to all nodes in the next time step.
As you indicate, it may not be easy to solve with SDDP. Is there any other solver you know of which may be able to solve this problem? Thank you!
I don’t belive the current literature solves it with SDDP
Ah…
I don’t think you should put effort into attempting to solve this model with SDDP.jl, and I’m not aware of any other algorithm that you can use.
It fundamentally can’t be decomposed by time because the decisions to be made in a node depend (via a constraint, not the objective) on the decisions that are made for every possible realization of the uncertainty in the next time-step. This also hints at which the literature solves this problem with much smaller problems…
I would instead consider alternative formulations that you could investigate that yield similar behavior and yet are more amenable to computation.
As one example, you might add \eta as a state variable, and penalize or constrain ||\eta_m - \eta_n||. This would work because it requires adding only one state variable (instead of 8*8) and it doesn’t require knowing the full distribution of the noise in the next time-step (since \eta_m happened in the past and you know exactly what it is).
