is there any approach to speed up the LP optimization?
Awaiting user input
Hi,
I am using piecewise linearization to simplify a MINLP problem. This problem was solved by several months ago, by using second order cone programming as a relaxation approach. However, when I recently went back to check some of the results and found they are not in very good solution and that's why I am trying to using linearization.
As the case is quite complex, the calculation is very slow, and I know it was due to thousands of binary variables. So I split the model into two part and find the feasible solution of these binaries. Then I import these binaries to convert the problem a LP problem, however, the speed is still very poor.
I wish my case can be optimised within 5-10 mins, as there is no nonlinear constraints and binaries. And also the number of continuous variable and constraints are not very large.
So how can I find the bottleneck and improve the speed of the optimization?
Many thank
Cass
-
Hi Cass,
You should try the latest Gurobi version 9.5.2 first. Maybe it is already enough.
In the screenshots you provided, the model is not an LP as it has 2832 general constraints. I guess these come from the piecewise linearization approach correct? Did you try worsening your linearization a bit to lower the number of binary variables?
Does your model struggle to find a feasible solution? If yes, then you could try experimenting with the NoRelHeurTime and Heuristics parameters.
The documentation of the most important parameters for MIPs might be helpful here.
You could also share your model. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 -
Hi Jaromił
Many thanks for your feedback. I don't know why general constraints here means that the model is not LP? Also, why do PWL linearization add some binaries into the model? Now there is only two segments in linearized expression of each nonlinear variables, so continuing reduce the segments is not very good at the moment.
Finally, yes, the model is extremely hard to find a feasible solution, I will update some of results if there is still no improvement once I tried NoRelHeurTime and Heuristics.
A screenshot below gives the model, and it will be perfect if you can have any advise on that.
0 -
Hi Cass,
I don't know why general constraints here means that the model is not LP?
General constraints add binary variable to formulate the requested function/formula/expression. Your model seems to have any of Gurobi's general constraints. This is stated in the log
Model has 2832 general constraints.
These general constraints are reformulated and binary variables are introduced. The log states this
Presolved: 13353 rows, 13497 columns, 42670 nonzeros
Variables types: 10955 continuous, 2452 integer (2452 binary)Thus, the model you currently solve is not an LP.
Also, why do PWL linearization add some binaries into the model?
I assumed that you use some standard piecewise-linear formulation, such as the one discussed in How do I model piecewise-linear functions? But this does not seem to be the case, so you probably don't have to use any binary variables for your linearization.
You could share an MPS or LP file of your model to make it easier to have a look. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 -
Hi Jaromił
I have just upload a MPS file numbered123, can you find that? If not, how can I share that with you?
Best
Cass
0 -
Hi Cass,
Thank you for the file. We received the file. I'll have a look and let you know if I can find something.
Best regards,
Jaromił0 -
Hi Cass,
It looks like the model has been generated using Gurobi's automatic PWL feature. In this case, Gurobi will automatically introduce binary variable to construct the PWL functions. If you want to avoid the addition of binary variables, you have to construct the PWL approximation constraints manually.
Note that the feasibility issue can be caused by the fact that the PWL approximation is too weak. From what I understand you are approximating the quadratic function by only 2 linear segments. This may not be enough to make the original model feasible, i.e., the approximation may not be good enough to find a feasible point withing error tolerances of the PWL approximation.
In your case, I would try to stick to the quadratic formulation instead of using PWL approximations. Could you share the quadratic formulation as an MPS/LP file as well?
Best regards,
Jaromił0 -
Hi Jaromił
Please have a look on this
Many thanks
Cass
0 -
Hi Cass,
I cannot access the new file. I am getting an access denied error.
Best regards,
Jaromił0 -
Yes, this works. Thank you.
Do you know whether it would be valid to formulate the quadratic equality constraints as inequalities? This would mean to use \(Q^2 \geq K^2 + P^2\) instead of \(Q^2 = K^2 + P^2\).
0 -
Many thanks Jaromił, I had a try on this. Seems the iteration time of each step decreased. Not sure if it works (7mins already now), the MPS file is attached and I will be grateful if you could please have look.
Using the inequalities means a relaxation? but how to prove that the solution tend to be closed to the practical value?
Best
Cass
Css
0 -
Using the inequalities means a relaxation? but how to prove that the solution tend to be closed to the practical value?
It is not necessarily a relaxation if the objective pushed the variables in the correct direction. I don't know enough about your model to tell whether it the \(\leq\) is valid. It was just an idea.
0 -
Yes, I agree with that, its a reasonable idea, as the objective function (minimize) will push the Q in right direction. But it seems the not very fast in finding the feasible solution.
Best
Cass
0 -
Your model looks highly symmetric. Is it possible to add an ordering of variable values on the quadratic variables into your model? For example,
C24(4) <= C48(4)
or
C2400(2) <= C2401(2)
The above variable names refer to variable names in the MPS file you provided. You could generate an LP file for human readability.
Best regards,
Jaromił0 -
Sure. Note that I don't know your model in detail so this is only a very vague idea.
In symmetric models, one runs into the issue that a solution point \((x,y)\) has the same solution value as the point \((y,x)\). If this symmetric is not recognized by the solver, which might be the case for quadratic models, it really slows down convergence for a number of reasons. In such cases, one tries to help the algorithm by introducing so called symmetry breaking constraints. The easiest form of those constraints is a simple ordering of variables. For the simple example, if we introduce a constraint \(x \geq y\), one of the points \((x,y),(y,x)\) with \(x\neq y\) becomes infeasible. This can often improve the solution process.
Best regards,
Jaromił0 -
I think I am now understand the approach, but generally, how can I add the ordering of these variables, is there any cases that I can learn something from? Variables in my model are already indexed by a 2D set ((i,t) or (a,t)), so how can I add the symmetry breaking constraint?
Many thanks
Cass
0 -
I think I am now understand the approach, but generally, how can I add the ordering of these variables, is there any cases that I can learn something from?
This is where it is up to the modeler (you) to use your problem knowledge and check whether there is symmetry in your model and how it can be broken.
Variables in my model are already indexed by a 2D set ((i,t) or (a,t)), so how can I add the symmetry breaking constraint?
For the model snippet you showed, this might look something like \(P_{i,t} \geq P_{j,t}\).
0
Please sign in to leave a comment.
Comments
18 comments