The No Relaxation heuristic (NoRel) is a proprietary heuristic developed by Gurobi. It is primarily intended for use with integer programming models where the root LP is challenging to solve. Such difficulties may arise when the model is large, numerical issues are present, or the model is ill-conditioned. However, NoRel can also help find good solutions for medium-sized combinatorial problems with many binary decision variables.
NoRel is unique in several aspects. It is currently the only one of Gurobi's heuristics that is not run by default and must be triggered through user parameters—namely NoRelHeurTime or NoRelHeurWork. It does not rely on the prior computation of a full LP relaxation, like many other heuristic approaches, nor does it rely on the availability of feasible solutions. For this reason, it can be particularly useful when finding a feasible solution is proving difficult.
Currently, when NoRel is used, it will run after the presolve phase but prior to solving the root relaxation. It is initialized with a heuristic "solution" - typically an infeasible and suboptimal solution - and various sub-MIPs are solved which are pieced together to create new solutions. Sub-MIPs can be solved in parallel, which results in NoRel scaling as well as the number of available threads increases.
When NoRel is initialized with an infeasible solution, it proceeds to perform "Phase 1" of the algorithm. This phase tries to minimize the violation of constraints and variable bounds. The objective value reported during this stage quantifies how far from feasible the incumbent solution is. When the objective value reaches 0, a feasible solution has been found. NoRel then moves to "Phase 2", in which the algorithm attempts to improve the solution with respect to the original objective function. If NoRel is initialized with a feasible solution - such as one found by a heuristic running in parallel to the presolve routine, or one provided by the user - then the first phase will be skipped.
Below is an example of output related to NoRel in a Gurobi log file.
... Presolve removed 78635 rows and 100586 columns Presolve time: 3.24s Presolved: 89026 rows, 68388 columns, 415646 nonzeros Variable types: 65646 continuous, 2742 integer (2742 binary) Starting NoRel heuristic Found phase-1 solution: relaxation 2.36461 Found phase-1 solution: relaxation 2.2535 Found phase-1 solution: relaxation 1.87255 Found phase-1 solution: relaxation 1.86223 Found phase-1 solution: relaxation 1.55556 Found phase-1 solution: relaxation 1.13796 Found phase-1 solution: relaxation 1 Elapsed time for NoRel heuristic: 6s (best bound 11) Found phase-1 solution: relaxation 0.222499 Found heuristic solution: objective 30402.721977 Transition to phase 2 Elapsed time for NoRel heuristic: 14s (best bound 11) Found heuristic solution: objective 30401.721977 Found heuristic solution: objective 26937.909458 Found heuristic solution: objective 25535.655508 Found heuristic solution: objective 18710.046881 Found heuristic solution: objective 9462.5930314 Found heuristic solution: objective 7478.5637874 ...
Frequently asked questions:
When should I use NoRel?
Although intended for problems with difficult root relaxations, NoRel can also work quite successfully for problems where the root relaxation is easily solved. Consequently, it would be worthwhile to experiment with NoRel (and make an accurate comparison) for most problems.
How long should I run NoRel for?
It is not unusual to see the solutions found by NoRel rapidly improve but then taper off into a plateau. The best solution from NoRel will be used in the branch and bound phase of the standard MIP algorithm and will be improved at a different rate. If the improvement rate of the branch and bound phase is slower, then we would say that NoRel was terminated too early. If the improvement rate of the branch and bound phase is faster, then we would say NoRel was terminated too late. Attempting to estimate a good value for either NoRelHeurTime or NoRelHeurWork is ideally done by building a case through experimental evidence and analyzing the data of many log files through a tool such as gurobi-logtools. Of course, it may be (and often is) that the best option is not to run NoRel at all.
What parameters affect NoRel?
The only parameters that directly affect NoRel are NoRelHeurTime and NoRelHeurWork. However, the NoRel algorithm requires many sub-MIPs to be solved, and consequently, most MIP-related parameters will indirectly affect the performance of NoRel. Additionally, since NoRel works on the presolved model, all parameters affecting the presolve phase also affect NoRel indirectly.
What is the best bound that is being reported in NoRel output?
When NoRel is running, there will be log lines that report a "best bound." This is a valid dual bound, but it is not produced by solving a full LP relaxation, and as a result, it can often be quite weak. However, we have also observed many cases where the reported bound is as good as the bound obtained by solving the full root relaxation (but it will never be better).
Why did NoRel not use my MIP Start?
A user who submits a MIP Start to Gurobi may be surprised to see NoRel enter Phase 1 instead of skipping straight to Phase 2. This can occur when the MIP Start solution is valid with respect to the original model but not valid with respect to the presolved model - i.e. the solution does not belong to the "presolved space" (considering the specified tolerances). Note that this may also happen in runs where NoRel is not used.