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 ...

• Gurobi Staff

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,
David

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.

• Gurobi Staff

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:

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,
David

Thank you. My next step is giving Gurobi a long time to tune a smaller version of the model.