I attempt to define a mixed-integer optimization problem. To simplify the problem:
I have 10 wind turbines. I have 10 boolean variables that indicate whether the turbine is operating at full or partial power. If it is operating at partial power, it needs a power set value between zero and 100% of the demand. So I have another 10 real variables to optimize. The demand is time varying. The optimization goal is to ensure that demand matches production.
So I have 20 variables. But if some of the Boolean variables are true, then the real value (relative power) of the related turbine does not need to be optimized.
If I define the system in this way, I am concerned that the optimization time may be less than optimal. Can I define the problem in a way that if one of the boolean variables is true, the associated real variable is ignored?
I guess you have some constraint making this impractical but the normal approach would be to do away with the booleans and only optimize the relative power values. Then you can infer your booleans from the result.
Why do you need the boolean variables, then? Why not simply let the degrees of freedom be the power % values, bounded \in [0, 100]?
Adding boolean variables doesnât seem to add anything to your problem, and makes the problem strictly harder (it is much harder to do optimization with discrete parameters than with continuous differentiable parameters).
Then why not make the parameter the % of the maximum power? Let the optimization keep this ⤠demand if thatâs what is optimal. Or some other variation on this ⌠hard to say without knowing more.
You should generally try hard to frame your optimization in terms of differentiable continuous parameters if at all possible. The whole trick in optimization is often to think more carefully about the problem formulation, rather than taking the problem formulation as a given and spending your time thinking about algorithms.
Not possible, because the parameter I am optimizing is not time-dependent. If I were to make it time-dependent, I would end up with many more variables to optimize. So, I have only three parameters to model the time dependency using a spline, and then one parameter per turbine, representing how much it shall contribute to the total demand.
Okay, what I could do is say that the parameter should be between zero and 2. One would mean 100% of the current demand, and 2 would mean always on.
import JuMP
import Random
Random.seed!(1)
G = 3 # num of generators
P = [
(m = 2, M = 6),
(m = 1, M = 7),
(m = 3, M = 8),
] # power range of generators
T = 4 # num of planning stages
D = [10, 20, 4, 16] # demand at each stage
model = JuMP.Model()
JuMP.@variable(model, b[1:T, 1:G], Bin)
JuMP.@variable(model, p[1:T, g = 1:G] ⤠P[g].M)
JuMP.@constraint(model, [t = 1:T, g = 1:G], b[t, g]P[g].M ⤠p[t, g])
JuMP.@constraint(model, [t = 1:T], D[t] ⤠sum(p[t, :]))
If you use efficient reverse-mode differentiation, having lots more optimization parameters is not necessarily a problem. The dominant cost is often the number of physics solves, which remains the same regardless of the number of parameters.
Be careful not to make your objective function non-differentiable in the parameters.
One possibility would be to relax your always_on boolean variable to a quantity a \in [0, 1], while also having another continous variable p \in [0, 1] representing the âpartial powerâ percentage of demand. Then set the actual power to be something like
P(t) = \max \{ p D(t), a P_{\max} \}
where P_{\max} is the maximum power and D(t) \in [0, P_{\max}] is the demand. This is still non-differentiable because of the max, but you could relax that further with a softmax to get a differentiable approximation.
But it also may not be terrible to simply make the time-dependent power the variables and just have a lot of differentiable optimization variables, if you are careful about how you compute derivatives, as I said above.
So I donât think I have any differentiable variables. Wakes can suddenly change their direction even if one of the control inputs changes only a tiny bit.
One function evaluation needs about 1-2 seconds; therefore, I try to keep the number of function evaluations below 10000.
Why does that make it non-differentiable? If itâs a nonlinear system of ODEs \frac{du}{dt} = f(u,t,p) and the rhs is a differentiable function of the parameters p, then so is the solution u(p,t).
Well, if the output (the mean square error between the desired and the produced power) jumps when you change one of the control parameters, I would say then it is not differentiable. There might even be some hysteresis.
Is there any systematic way to determine if a problem is differentiable?
In a nonlinear ODE, the steady-state (t \to \infty) solution can jump discontinuously as you change a parameter, but I donât see how the finite-time behavior can be discontinuous (assuming the rhs is differentiable), even if it changes rapidly?
(Hysteresis is also about jumps in the steady state.)
Indeed, for \frac{\partial u}{\partial t} = f(u,p,t) where the rhs is differentiable in u and p, you can write down an explicit linear ODE that is solved by the Jacobian \partial u/ \partial p, in which all of the terms are finite. (See e.g. section 9.2.1 of our matrix-calculus course notes.)
Isnât this just an ordinary optimal control problem?
So if p is your power production and d the demand, you would have:
p \in [p_{\min}, p_{\max}]
With p_{\min} being 0, and p_{\max} = d. I donât see why you would need binary variables at all? Or are you are in a situation where p_{\min} > 0 and p \in {0} \cup [p_{\min}, p_{\max}]?
In that case I only know sub-optimal tricks and I would also be interested in learning more of those.
Not sure if this is obvious, but the most typical thing to do here in mixed integer optimization is to introduce linear constraints such as
isfullpower = @variable(model, 1:10, Bin)
power = @variable(model, 1:10, 0 <= x[1:10] <= 1)
@constraint(model, power .>= isfullpower)
(typed on my phone, havenât run it)
So this will force the power to be max when the binary variable is set to 1 (i.e., it will be âignoredâ in the optimization), and enforce no constraint otherwise.
To get efficient optimization itâs important to avoid nonlinearities (e.g., power .* isfullpower) but thereâs very efficient algorithms for this formulation based on branch-and-bound and âcutsâ in the search space.
Gurobi is (one of) the leading optimizers for mixed integer programming.
Perhaps youâre saying by allowing any discrete variables at all weâre losing a lot of optimization performance? That may be true, but many things are fundamentally âinteger valuedâ.
Solving an MIP typically has a convex phase (root LP relaxation, adding cutting planes), followed by a branch-and-bound phase. The former is efficient, whereas the latter is not. Its difficulty is inherent, regardless of which solver you go with.
In practice itâs highly problem-dependent. Some problems, despite might look large, may be efficiently solved, whereas some are not.
It is easy to create an MIP instance that let Gurobi struggle in its branch-and-bound phase. e.g.
Integer variables should be added only when they are necessary.
By the way, @ufechner7 your title is too big, that attracts everyone to take a look.