Non-linear optimisation
Answered
Hello guys, could you please explain how far can Gurobi go with no-linear optimization? There is this link:
https://www.gurobi.com/documentation/9.5/examples/qp_py.html
and this one:
https://www.gurobi.com/documentation/9.5/refman/py_model_agc_xxx.html
Are those the boundaries? for example, if I had in the objective function
x/y or x^y where x,y are variables I should not expect to solve this kind of problem right?
Also when we have non-linearities do we loose optimality also? is running time increased as well?
Kind regards
Iason
-
Hi Iason,
Hello guys, could you please explain how far can Gurobi go with no-linear optimization?
With version 11.0.0 Gurobi supports solving non-linear models using spatial branch-and-bound and outer approximation as an alternative to the static piecewise-linear approximation of non-linear constraints supported in earlier versions. Please refer to the documentation of general constraints for more details.
Webinars about nonlinear optimization in Gurobi are coming soon.
Starting with version 9.0.0 Gurobi supports nonconvex quadratic models, i.e., the only nonlinear functions accepted before were \(x\cdot y\) and \(x^2\).
For more information about how Gurobi deals with (nonconvex) quadratic functions, please refer to
- Non-Convex Quadratic Optimization webinar
- Nonconvex Quadratic Optimization with Gurobi
- A Practical Tour Through Non-Convex Optimization - Tech Talk
Are those the boundaries? for example, if I had in the objective function
x/y or x^y where x,y are variables I should not expect to solve this kind of problem right?You can model the reciprocal as discussed in the Knowledge Base article How do I divide by a variable in Gurobi? The term \(x^y\) can be rewritten as \(\exp(y \cdot \log(x))\) and then formulated via the piecewise-linear approximation functions addGenConstrExp and addGenConstrLog. Please note that tight variable bounds are always necessary when working with highly nonlinear expressions. This is to allow Gurobi to compute a good piecewise-linear approximation of the original function.
Also when we have non-linearities do we loose optimality also?
No, we do not lose global optimality. Gurobi is a global solver, meaning that it will try to prove that no better solution exists up to the requested MIPGap.
is running time increased as well?
Yes, usually the running time is increased. However, this strongly depends on the complexity and size of the nonlinear model.
Best regards,
Jaromił0 -
Thanks Jaromił.
0 -
Hello Jaromił,
Is there any way that I can model the following constraint?:
Where R and U are variables.
Also I am wondering if I can model the following constraint:
where x_a is a variable and P_a t_{0,a} are parameters.
and then if I can calculate the above can I calculate in my objective function:
Kind regards
Iason
0 -
Another question I forgot to ask: Gurobi can calculate x*x but does this mean that It can calculate x*(x-5)? Can It calculate any formula as long as the power is up to 2?
Kind regards
Iason0 -
Hi Jaromił,
A possible solution that I am considering is to create a function g that takes as input R_i and R_w and returns the difference of their logs. And then set it equal to U_i-U_w as a constraint of the model. Would such thing work? (trying to incorporate the non-linearity in the function that will yield a result in the constraint)
and another possible solution for the second example that I am considering is to create a function f that calculates t_a with the input of x_a and then I could use this function f in the objective function to make this multiplication. Am I on the correct path?
Kind regards
Iason0 -
Hi Jaromil,
I have found a modeling way to surpass all those I have this problem though:
How can I model a logarithm that takes parameterized variables?
Could you help me to make this code work? first two lines define the variables. How can I establish a log relationship between them?Rirs = model.addVars(I, drs.keys(), lb=0, ub=1, vtype=GRB.CONTINUOUS, name='R_i^rs')
lRirs = model.addVars(I, drs.keys(), lb=0, ub=1, vtype=GRB.CONTINUOUS, name='lR_i^rs')
model.addGenConstrLog(Rirs[i,r,s] , lRirs[i,r,s] for i in I for r,s in drs.keys())kind regards, Iason
0 -
Hi Jaromił, my code is in this folder in dropbox:
https://www.dropbox.com/scl/fo/0w8bt6jue8dn5cykewa94/h?dl=0&rlkey=2h1vvq0plpt8b6rl8pepehtosThere are 2 excel files that it reads. You do not have to go through the whole code. You can just run it up to line 370. Just change the initial link to the folder that you put the excel files. Im saying this to help you. If you know the answer of how to form this type of logarithmic constraint you can just let me know without looking at my code to speed up.
Kind regards
Iason0 -
Hi Jaromił, I think I have found the solution. I have put a one note with the explanation and my question in the Dropbox link. And the new version of my code named Benders new. The modeling explained in one note is on the code line 350. Could you take a look to confirm if this is correct? Basically, I'm wondering if the variable parameters of a constraint pass through the log constraint since we cannot have parametrized variables in the log constraint. I explain my question better in the one-note file. If you have any questions feel free to ask me. You do not need to go through my whole code. If you want you can run it up to the constraints on line below 350.
https://www.dropbox.com/scl/fo/0w8bt6jue8dn5cykewa94/h?dl=0&rlkey=2h1vvq0plpt8b6rl8pepehtos
Kind regards
Iason0 -
Hi Iason,
Sorry for not coming back to you earlier.
I had a look at your notes in file \(\texttt{Benders_new.py}\) at around line 350. What you are modeling is
\[\begin{align*}
x_1 &= Rirs_{i,r,s} \quad \forall i,r,s\\
y_1 &= lRirs_{i,r,s} \quad \forall i,r,s\\
y_1 &= \log(x_1)
\end{align*}\]So you force all \(\texttt{Rirs[i,r,s]}\) and \(\texttt{lRirs[i,r,s]}\) variables to be equal. I think what you are looking for is
for i in I:
for r,s in drs.keys():
model.addGenConstrLog(Rirs[i,r,s], lRirs[i,r,s])Best regards,
Jaromił0 -
Thank you so much Jaromił.
Kind regards Iason0 -
And for this case, I would have to include model.setParam('NonConvex', 2) because log function is concave right?
Kind regards
Iason0 -
Hi Iason,
And for this case, I would have to include model.setParam('NonConvex', 2) because log function is concave right?
The \(\log\) function is formulated via piecewise-linear approximation by Gurobi. Thus, in the end, the model is a MIP. So unless you have other terms where you use nonconvex terms \(x\cdot y\) or \(-x^2\) then you should not have to set the NonConvex parameter.
Best regards,
Jaromił0 -
thank you Jaromił
0 -
Hello Jaromił,
I have one more question. The video presentations, you sent me have the following transformation:
My question is: are those transformations good to have? 0bligatory? or are they made by Gurobi? Because I do not see such transformations in the standard pooling problem or the decentralization planning.
Kind regards
Iason0 -
Hi Iason,
Sorry for not coming back to you earlier.
My question is: are those transformations good to have? 0bligatory? or are they made by Gurobi? Because I do not see such transformations in the standard pooling problem or the decentralization planning.
What you see on the slide is the algorithmic part of nonconvex optimization. This is what Gurobi does automatically behind the scenes and you as a user don't have to worry about it.
This is the reason why you almost never see such reformulations when looking at specific problems such as pooling. It is just not the natural way to formulate models but it is very convenient when working with the model on the algorithms side.
Best regards,
Jaromił0 -
Thanks Jaromił
0
Please sign in to leave a comment.
Comments
16 comments