Need help on understanding the NoRelHeurTime parameter
Answered
Hi everyone,
I've been solving a class of binary linear programming (BLP) problems with no objective function. I seek a single feasible solution. I've found acceptable runtimes using Gurobi v 10.0 when I use the NoRelHeurTime for appropriate values that are problem specific. (I also set MIPFocus = 1 and SolutionLimit = 1, although I don't think these parameters help that much if at all.) Without setting this parameter the runtimes are often very long.
My first question is, what exactly is Gurobi doing in the NoRel phase of the solution? How is this different from the Branch-&-Bound (B&B) solution techniques?
My 2nd question is as follows: I have a VERY large BLP problem (> 10^6 unknowns) that was not solved in over 6 months (I was not using the NoRelHeurTime parameter). I suspect my problems scale so badly that the B&B might run for years without finding a solution. Is there a chance that if I set NoRelHeurTime to infinity I might get a solution in a reasonable amount of time? I thought this might be worth a try as the NoRel phase of the solution process is fundamentally different from the B&B phase.
Thank you,
Marcus
-
Ok, I can add a bit more information to this question. I tried the strategy of setting NoRelHeurTime to infinity for my very big BLP problem and ran it over night. I then plotted relaxation numbers against time. (Based on the behaviour when this heuristic was used on smaller problem I know that when I get a solution the relaxation number should go to zero). The graph is not encouraging ...
0 -
Hi Marcus,
There is a very good reply from Xavier about our NoRel heuristic:
Some details about the NoRel heuristic appear at https://support.gurobi.com/hc/en-us/community/posts/9282521673745-What-is-phase-1-solution-. I know that you were already aware of this post, as you commented in it. But I mention it here for others who may not have come across it.Let me add other information. In phase 2, when it has a feasible solution, NoRel tries to improve it. But that improvement process is incomplete, and NoRel may not find better solutions that exist, even if given more time. This is the reason why the time (or number of work units, to keep a deterministic behaviour) to spend on NoRel has to be specified by the user. Given that the time is specified by the user, it wouldn't really add much information if Gurobi would display the remaining time.The NoRel heuristic runs before the root node is computed, and Gurobi may not know a lower bound to compute a gap.Is your plot showing the phase 1 stage, the heuristic values of phase 2, or the relaxation of phase 2?If it is the latter then this is not very helpful as NoRel does not compute the relaxation fully, it is used to obtain integer feasible solutions, and the relaxation solutions are a by-product. If you want to obtain an indicative MIP gap, you can allow enough time to solve the relaxation after NoRel.What happens if you set TimeLimit to something larger than NoRelHeurTime? i.e. let the standard Gurobi solve run for a bit. Apart from an indicative MIP gap, it may happen that with a good starting solution, the standard solve is able to quickly improve.Cheers,
David0 -
Thank you. My plot is showing only the phase 1 stage. With regard to your second question, as I mentioned, if the time is greater than the NoRelHeurTime Gurobi runs basically indefinitely. I was investigating the phase 1 stage because I have no objective function and I only want a single feasible solution.
0 -
Hi Marcus,
Thanks for the explanation, I get it now.
Unfortunately, as NoRel seems to be stuck in phase 1 indeed this is not a very hopeful option for your model.
Have you tried any of our other non-default heuristics:- ZeroObjNodes
- PumpPasses
- or, MinRelNodes
- or, even the PartitionPlace (this one is slightly trickier)
They might also be effective for your problem, to try them out just set the parameter to a high value and you should see it in the log. They run as part of the BnB search so there is also some hope for solutions via branching.
Cheers,
David0 -
Thank you. My next step is giving Gurobi a long time to tune a smaller version of the model.
0
Please sign in to leave a comment.
Comments
5 comments