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 MIP 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 you should only consider it 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 HEUREMPHASIS control. The default is that all heuristics run according to their individual controls. The interpretations of the settings of HEUREMPHASIS are roughly:

-1 – Default heuristics.
0 – Disable all heuristics.
1 – Focus on reducing the primal-dual gap in the early part of the search. This addresses problems where the goal is to achieve a small gap but not neccessarily solving them to optimality.
2 – Extremely aggressive search heuristics. Good for some problems.

In the output log, single letters at the start of the line indicate a heuristic solution, 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 letters at the start of the line 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. A similar control, HEURSEARCHFREQ, exists for local search heuristics.

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 for the tree solve. It is possible to override this selection by setting HEURDIVESTRATEGY to a value from 1 to 18. Testing all diving strategies is part of the TUNERTARGET=8 setting.

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 run on the root problem, at most 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 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 high-quality solutions quickly, we recommend setting HEUREMPHASIS to 1 or even 2. Alternatively, you could try to find a specific combination of HEURSEARCHROOTCUTFREQ, HEURSEARCHFREQ, HEURSEARCHROOTSELECT and HEURSEARCHTREESELECT that works best for your problem.

Running heuristics is particularly useful when the branch-and-bound tree search has to dive to considerable 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

HEUREMPHASIS

Select how much emphasis to put on primal heuristics (0 off to 3 aggressive).

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.