Adding a few variables and constraints makes the model nearly unsolvable
Answered
Hi all,
I have a power systems optimization model. It is pretty large model, but Gurobi did not have any problem to solve it in 4 hours. This was the situation a few weeks ago. Below, you can see the number of variables and constraints before and after pre-solve procedure.
I recently added a few decision variables (126 continuous and 42 binary) and constraints. Gurobi can not solve this new model in 22 hours. Below, you can see the number of variables and constraints before and after pre-solve.
So, previously, there were 1,541,716 continuous decision variables before pre-solve. I added 126 continuous variables and total number of continuous decision variables turned out to be 1,541,842 in new model. This is correct. Similarly, there were 369,640 integer variables. I added 42 binary variables to the model and total number of integer variables turned out to be 369,682. This is correct too.
What I do not understand is the big difference in number of integer variables after pre-solve in two models. Previously, there were 251,215 integer variables after pre-solve. In the new model, this number is 369,115. Why is this happening? I assume that this is the reason why Gurobi can not solve the recent model in a reasonable amount of time. Again, previous model was solved by Gurobi in 4 hours. However, the recent model can not be solved in 22 hours. 22 hours is the time limit I put for Gurobi. All 22 hours were spent for root relaxation. I do not event see the log for branch and bound tree.
Can you please help me with this?
Kind regards,
Fikri Kucuksayacigil
-
Hi Fikri,
It is not uncommon that adding just a few variables can significantly increase the solving time for a model. Also, please note the vastly increases ranges in matrix coefficients and the right-hand sides.
Maybe you can share a slightly longer excerpt of a log that shows where Gurobi is struggling. You might also want to check out Gurobi/grblogtools: Extract and visualize information from Gurobi log files (github.com) to better interpret the solver's progress.
Cheers,
Matthias0 -
Hi Matthias,
I am sorry for my delayed answer. I have been traveling, and have been busy to finish accumulated tasks after I returned.
After several trials of playing with Gurobi parameters (Method, MIPFocus, ImproveStartGap, etc.), and even making the model smaller, I have still this issue. My overall problem is that the algorithm has a difficulty in shrinking optimality gap. It sticks and never progress.
As you pointed, I think I have to deal with numerical issues. I have "Sub-optimal termination for barrier" and "Markowitz tolerance ..." warnings in the log. I know that you can not give me specific advise, but what do you think about how I should target numerical issues when you look at objective range and matrix coefficient range? RHS range seem also large.
Thank you
0 -
Hi Fikri,
Most importantly with respect to numerics is the large matrix range from 3e-6 to 2e+8. This is almost certainly going to cause issues during solving.
You should try to get that range down by employing different scalings for your variables. Maybe you can exchange some units (centimeters to kilometers, grams to kilos, etc.) to make those numbers more homogeneous.
Please refer to our Guidelines for Numerical Issues.
I hope that helps.
Cheers,
Matthias0 -
Hi,
Thank you so much. I forgot to say that I had got rid of big-M constraints before, and current matrix ranges are
Do you think it is still problematic? According to Gurobi parameter guidelines, matrix range should be at most 10^9 and objective should be in 10^4. In this case, I am at the limit for matrix range and terrible shape in objective range. Am I right?
I have an idea to change the units by the way. I may apply it.
Kind regards
0 -
Hi,
After several attempts for scaling the model and tweaking Gurobi parameters, I solved some of the issues, but the finding an optimal solution faster is still problematic. I think I will open another issue, and report everything that I did and what they resulted in.
Kind regards
0 -
For reference, here is the link to the separate post: How to make the search over B&B tree faster? – Gurobi Support Portal
0
Please sign in to leave a comment.
Comments
6 comments