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.

There are a few controls that affect all of the heuristics:

HEURSTRATEGY

Determines the level of heuristics to use. A value of 3 will allow all heuristics to be run and a value of 1 will only allow the faster rounding and diving heuristics to be run. Setting HEURSTRATEGY to 0 will disable all heuristics.

HEURTHREADS

The number of additional heuristic threads to start in parallel with cutting on the root node. If set to zero, heuristics will be run interleaved with cutting.

The simple rounding heuristics do not have any controls associated with them. 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.