Working with Heuristics

The Optimizer contains several primal heuristics that help to find feasible solutions during a global search. These heuristics fall broadly into one of three classes:

1. Simple rounding heuristics
   These take the continuous relaxation solution to a node and, through simple roundings of the solution values for global entities, try to construct a feasible MIP solution. These are typically run on every node.
2. Diving heuristics
   These start from the continuous relaxation solution to a node and combines rounding and fixing of global entities with occasional reoptimization of the continuous relaxation to construct a better quality MIP solution. They are run frequently on both the root node and during the branch and bound tree search.
3. Local search heuristics
   The local search heuristics are generally the most expensive heuristics and involve solving one or more smaller MIPs whose feasible regions describe a neighborhood around a candidate MIP solution. These heuristics are run at the end of the root solve and typically on every 500–1000 nodes during the tree search.

Some simple heuristics and a few fast diving heuristics, which do not require a starting solution, will be tried before the initial continuous relaxation of a MIP is solved. On very simple problems, it is possible that an optimal MIP solution will be found at this point, which can lead to the initial relaxation being cut off. These heuristics can be enabled or disabled using the HEURBEFORELP control.

The most important control for steering the overall heuristic behavior of the Optimizer is HEUREMPHASIS Setting this control to 1 will trigger many additional heuristic calls. This setting typically leads to a quicker reduction of the optimality gap at the beginning of the search. However, it often comes at the expense of the running time to proven optimality increasing. Consequently, we recommend this setting for use cases that aim to find a reasonably good solution quickly but for which proving optimality is out of scope.

Setting HEUREMPHASIS to 2 will enable a very aggressive heuristic behavior. While this can be beneficial for some problems, it is on average inferior to the more balanced setting of 1. Setting HEUREMPHASIS to 0 will disable all heuristics. This replaces the deprecated HEURSTRATEGY=0 setting.

In addition to running the solver with a heuristic emphasis from the beginning, a secondary application of HEUREMPHASIS is solution polishing. Therefore, the user would alter the heuristic emphasis only when the solve comes close to the intended time limit or the progress in the optimality gap stalls. This can, e.g., happen from a callback. Note that this is most promising when the solver has already made some significant progress in tree search. Especially for problems that spend a majority of the targeted solution time in the root node, we recommend setting HEUREMPHASIS=1 from the beginning.

There are a few other controls that affect heuristics. The diving heuristics have the following controls:

HEURFREQ

The frequency at which to run a diving heuristic during the branch and bound tree search. If HEURFREQ=k, a diving heuristic will be applied when at least k nodes of the tree search have been solved since the last run. Set this control to zero to disable diving heuristics during the tree search. With a default setting of -1, the Optimizer will automatically select a frequency that depends on how expensive it is to run and how many integer variables need to be rounded. Typically, this results in a diving heuristic being run for every 10–50 nodes.

HEURDIVESTRATEGY

Can be used to select one specific out of 10 predefined diving strategies, otherwise the Optimizer will automatically select which appears to work best. Set this control to zero to disable the diving heuristic.

HEURDIVERANDOMIZE

How much randomization to introduce into the diving heuristics.

HEURDIVESPEEDUP

The amount of effort to put into the individual dives. This essentially determines how often the continuous relaxation is reoptimized during a dive.

The local search heuristics have the following controls:

HEURSEARCHFREQ

The frequency at which to run the local search heuristics during the branch and bound tree search. If HEURSEARCHFREQ=k, the local search heuristics will be run when at least k nodes of the tree search have been solved since the last run.

HEURSEARCHEFFORT

Determines the complexity of the local search MIP problems solved and, if HEURSEARCHFREQ=-1, also how often they are applied.

HEURSEARCHROOTSELECT

Selects which local search heuristics are allowed to be run on the root node. Each bit of this integer control represents an individual heuristic.

HEURSEARCHTREESELECT

Selects which local search heuristics are allowed to be run during the branch and bound tree search.

The simple rounding heuristics do not have any further controls associated with them.