Heuristics

The Xpress Optimizer contains a wide variety of heuristics to help find feasible solutions during a MIP solve. They generally fall into one of the following three categories:

Simple rounding heuristics

Very fast heuristics that appliy some simple rules to the solution of the continuous relaxation in order to produce a feasible MIP solution. These are typically run on every node.
Specific controls: none

Diving heuristics

Start from the continuous relaxation solution to a node and combine 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.
Specific controls: HEURFREQ, HEURDIVESTRATEGY, HEURDIVESPEEDUP.

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 during the root cut-loop and typically on every 500 - 1000 nodes during the tree search.
Specific controls: HEURSEARCHFREQ, HEURSEARCHEFFORT, HEURSEARCHROOTSELECT, HEURSEARCHTREESELECT, HEURSEARCHROOTCUTFREQ.

In addition to these heuristics, the optimizer also contains a feasibility pump heuristic. It is off by default, and should mainly be considered when all other heuristics have failed to find a solution. It can be turned on by setting the FEASIBILITYPUMP control to either 1 (run always) or 2 (run when no MIP solution exists).

The set of heuristics that the optimizer should run can be set indirectly using the HEURSTRATEGY control. The default is to allow any heuristic to run, depending on the individual heuristic controls. The interpretations of the settings of HEURSTRATEGY are roughly:

In the output log, heuristic solutions are identified by a lower or upper case letter at the start of the line, such as in this example:

Starting root cutting & heuristics
 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap      GInf   Time
k           16.250000    11.204731      1                  31.05%       0      0
   1  K     16.250000    12.435740      1     58      0    23.47%      21      0
   2  K     16.250000    12.971545      1     71     94    20.18%      24      0
d           16.000000    12.971545      2                  18.93%       0      0
r           15.250000    12.971545      3                  14.94%       0      0
Heuristic search started
R           14.750000    12.971545      4                  12.06%       0      0
Heuristic search stopped

Here the first solution with objective value 16.25 was found by rounding heuristic strategy 'k' before the first round of cutting.

The letter at the start of the line can be used to identify the heuristic responsible for finding the solution. The following table helps map letters to heuristics, and the primary control for enabling or disabling the specific heuristic.

The diving heuristics are typically run between each round of cuts on the root problem and then once for every k nodes solved, where the frequency k is determined by the HEURFREQ control.

There are 18 preset diving heuristic strategies. The Xpress Optimizer will typically test 4-6 of them before and after the root problem cutting, and pick the most promising strategy to use for the tree solve. It is possible to override this selection by setting HEURDIVESTRATEGY to a value from 1 to 18. It is usually best to just try each in turn to learn which works best.

The local search heuristics rely on creating and solving a reduced MIP and can therefore be quite expensive to run. Normally, only two local search heuristics will be run on the root problem, and only every five cut rounds. During the branch-and-bound search, the local search heuristics will be run once for every k nodes, where the frequency k is determined by the HEURSEARCHFREQ control.

The Xpress Optimizer has several local search heuristics, but only some of them are on by default. The additional heuristics can be turned on using the HEURSEARCHROOTSELECT control (for the root problem) or the HEURSEARCHTREESELECT control (for the branch-and-bound search). These are both bit-vector controls where each individual bit is used to turn a heuristic on or off. The values of these bits are:

Bit 0

Local search with a large neighborhood. The default heuristic.

Bit 1

Local search with a small neighborhood, centered around the continuous relaxation solution.

Bit 2

Local search with a small neighborhood, centered around the integer solution. Default on for the root node only.

Bit 3

Local search with a neighborhood given by multiple integer solutions.

Bit 4

[unused]

Bit 5

Local search without an objective function. Typically expensive, but can be useful for finding a first solution. Applicable to the root only.

Bit 6

Local search with an auxiliary objective function. Typically expensive, but can be useful for finding a first solution. Applicable to the root only.

To test whether running any of these non-default heuristics is useful, it is best simply to turn all of them on and observe whether additional solutions are discovered. To do so, enable all the bits of HEURSEARCHROOTSELECT, by setting it to 127 (or equivalently -1).

When the emphasis is on finding good solutions quickly it is often beneficial to turn on more local search heuristics. If the local search heuristics work well, it might also be useful to run them more frequently. On the root node, the local search heuristics can be interleaved with cutting, using the control HEURSEARCHROOTCUTFREQ. This control specifies how many cutting rounds to skip before applying the local search heuristics. The default is to run local search heuristics only after all cutting has completed. During the tree search, the frequency by which local search heuristics are run can be adjusted with the HEURSEARCHFREQ control. The default is to run local search heuristics for every 250-1000 nodes. Values like 50 or 100 should be good ones to try.

Running heuristics is particularly useful when the branch-and-bound tree search has to dive to very large depths. Observe the "Depth" column of the following log segments:

Node     BestSoln    BestBound   Sols Active  Depth      Gap      GInf    Time
   1  1.32251E+11  1.32210E+11      3      2      1     0.03%     1897     348
...
  10  1.32251E+11  1.32210E+11      3      9      4     0.03%     1937     360
...
 100  1.32251E+11  1.32210E+11      3     11     93     0.03%     1827     442
...
1000  1.32251E+11  1.32210E+11      3     11    992     0.03%     1076     783
...
2000  1.32251E+11  1.32210E+11      3     11   1992     0.03%      581    1087
...
3000  1.32251E+11  1.32210E+11      3     11   2992     0.03%      408    1469

Here the "Depth" column keeps increasing, while the "GInf" column (number of fractional variables) steadily decreases. This is a sure indicator that the branch-and-bound solve is still on its first dive towards integer feasibility. Without heuristics, it will not find a new solution before the "GInf" column reaches zero. Heuristics can be used to find improved solutions at any point during this dive.

On the other hand, if the emphasis is on solving to optimality, heuristics have been found to have only a little effect on the overall solve time, except in special circumstances.

Finally, it is possible to increase the amount of effort put into each run of the local search heuristics, through the HEURSEARCHEFFORT control. The default value is 1.0 and increasing it to 2.0 is the equivalent of asking the heuristic to try twice as hard.

Heuristic Controls Summary

HEURSTRATEGY

Select how expensive heuristics to run (0 off to 3 everything).

HEURDIVESTRATEGY

Select one of the preset 10 diving heuristic strategies (0 off, or 1 10).

HEURFREQ

Run a diving heuristic for every HEURFREQ nodes solved.

HEURSEARCHROOTSELECT/HEURSEARCHTREESELECT

Bit-vector control to enable or disable specific local search heuristics, on the root problem or during the branch-and-bound search, respectively.

HEURSEARCHROOTCUTFREQ

How frequently to run local search heuristics between rounds of root cutting.

HEURSEARCHFREQ

Run a local search heuristic for every HEURSEARCHFREQ nodes solved.

HEURSEARCHEFFORT

Multiplier on the effort spent on local search heuristics.