Node exploration takes too long when constraints increase
AnsweredHello
I am using Gurobi to solve an LP on Julia/JuMP. The starting point was a simple linear model which converged in under a minute. A next step was to introduce piecewise linear constraints using the SOS2 methodology (https://jump.dev/JuMP.jl/stable/tutorials/linear/tips_and_tricks/#Piecewise-linear-approximations). When I run simulations after including this, Gurobi goes into the solution phase where it tries to reduce the MIP gap to below the tolerance although this is not a MIP model. In the attached screenshot, I have shown the terminal outputs of 2 cases - one with only 2 SOS constraints and the other with a lot. In the former, integer variables are somehow created after the presolve phase which I guess justifies Gurobi trying to reduce the MIP gap. Anyway, for this case, it exits this phase after the first iteration and the problem converges quickly. For the actual case with 17520 SOS constraints, integer variables are not created after pre-solve but Gurobi is still trying to reduce the MIP gap for some reason. This case does not converge and the terminal shows that there are no incumbent or gap values. Could you tell me what the issue is here? Increasing the number of SOS constraints beyond a threshold seems to the be the root cause.
-
Hi Ashwin,
The moment you introduce SOS constraints your model is no longer a LP, you have a discrete optimization problem.
SOS Constraints are either handled by reformulation into Big-M constraints (requiring the introduction of binary variables) or via branching. Either way the solution process will require a B&B tree. You can control how SOS constraints are handled with the PreSOS2BigM and PreSOS2BigM parameters.
On the screenshot on the left, presolve has reformulated all SOS constraints as Big-M constraints and introduced the required binary variables to do so. You can infer this because there is no mention of SOS constraints in the presolved model.
On the screenshot on the right, presolve has not reformulated any SOS constraints and they must be handled via branching. You can infer this because there is the same number of SOS constraints in the presolved model, and no binary variables have been introduced.
It is not surprising to me that a model with such a large number of SOS constraints may take a long time to find a feasible solution. Perhaps you could play around with the parameters above to see if it aids the solve.
It may also be worthwhile getting familiar with our documentation on Most important parameters including the information on our NoRel heuristic, which may prove useful here.
- Riley
1 -
Hi Riley
Thank you for your explanation and suggestions. I did play around with PreSOS2BigM, MIPFocus and Threads. While changing these did help a smaller problem, even with the "optimized" parameters, the original big problem is taking too long. I realise the issue I am having is pretty much exactly the same as this post.
Since they were unable to find a solution, I guess I woiuld also need to scale down my problem.
Thank you again.
0 -
No problem Ashwin, I'd also recommend the recording of our webinar:
Faster MIPs Using Custom Heuristics
You may find some inspiration in there on creating heuristics to construct a feasible solution or using our solver as the basis for a heuristic.
- Riley
0
Please sign in to leave a comment.
Comments
3 comments