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.

Large neighborhood search (LNS) heuristics

LNS heuristics involve solving one or more smaller MIPs whose feasible regions describe a neighborhood around a candidate MIP solution. They are generally considered the most expensive heuristics. These heuristics are run during the root cut-loop and typically on every 500 - 1000 nodes during the tree search.
Specific controls: HEURSEARCHFREQ, HEURSEARCHEFFORT, HEURSEARCHSTRATEGY, HEURSEARCHRINSSTRATEGY, 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).

For problems with very hard continuous relaxation, the Optimizer features the Pre-root parallel heuristic phase, which is disabled by default, but is enabled either through HEUREMPHASIS=2 or through the controls PREROOTEFFORT or PREROOTWORKLIMIT, respectively. If enabled, this phase runs a diverse strategy of combinatorial and sub-MIP heuristics in parallel on all available threads. The main work limit for this phase can be directly set via PREROOTWORKLIMIT. Using the PREROOTEFFORT control lets the Optimizer decide on a suitable work limit depending on the problem characteristics. Here, it is advisable to start with PREROOTEFFORT=1. In order to emphasize Pre-root parallel heuristics further or reduce the effort, set this control value to a value that is larger than 1/smaller than 1, respectively. In both cases the control value acts as a factor for the work limit decided with PREROOTEFFORT=1. The PREROOTTHREADS control can be used to specify a number of parallel threads. The default value uses all available threads, as decided by the THREADS control. The strategy in pre-root parallel heuristic phase benefits from more available threads. However, it might be necessary to tune down the number of threads used if the memory footprint of this phase becomes too large.

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, including pre-root parallel 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 LNS 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 LNS heuristics rely on creating and solving a reduced MIP and can therefore be quite expensive to run. Normally, only two LNS heuristics will run on the root problem, at most every five cut rounds. During the branch-and-bound search, the LNS heuristics will be run once for every k nodes, where the frequency k is determined either automatically based on the heuristic success, or by the HEURSEARCHFREQ control.

The Xpress Optimizer includes several large neighborhood search (LNS) heuristics. Each can be individually controlled through a strategy parameter that governs how frequently and aggressively it is run. The available LNS heuristics and their corresponding strategy controls are:

HEURSEARCHRINSSTRATEGY

RINS ( R): LNS heuristic with a large neighborhood. Potentially expensive but good for finding solutions that differ significantly from the incumbent.

HEURSEARCHLPFIRSTSTRATEGY

LP first ( L): LNS heuristic with a small neighborhood centered around a node LP solution.

HEURSEARCHMIPFIRSTSTRATEGY

MIP first ( M): LNS heuristic with a small neighborhood centered around an integer solution. Often provides smaller, incremental improvements to an incumbent.

HEURSEARCHCOMBINESTRATEGY

Combine ( C): LNS heuristic with a neighborhood set up through the combination of multiple integer solutions.

HEURSEARCHZEROOBJSTRATEGY

Zero Objective ( Z): LNS heuristic without an objective function. Useful for finding a first feasible solution.

HEURSEARCHANALYTICSTRATEGY

Analytic Center ( A): LNS heuristic with an auxiliary objective function. Useful for finding a first feasible solution.

Each strategy control accepts values -2 (XPRS_HEURSEARCHSTRATEGY_AUTOENFORCED), -1 (XPRS_HEURSEARCHSTRATEGY_AUTOMATIC), 0 (XPRS_HEURSEARCHSTRATEGY_OFF), 1 (XPRS_HEURSEARCHSTRATEGY_CONSERVATIVE), 2 (XPRS_HEURSEARCHSTRATEGY_MODERATE), and 3 (XPRS_HEURSEARCHSTRATEGY_AGGRESSIVE), where the strategy determines the frequency and effort of the heuristic. The value -2 behaves like -1 but protects the individual control from being overridden by HEURSEARCHSTRATEGY. The meta control HEURSEARCHSTRATEGY sets a uniform strategy for all LNS heuristics whose individual control is left at automatic. The effective frequency and effort also scale with HEUREMPHASIS.

When the emphasis is on finding high-quality solutions quickly, we recommend setting HEUREMPHASIS to 1 or even 2. For finer control, individual heuristics can be enabled at an aggressive strategy or tuned through a specific combination of HEURSEARCHROOTCUTFREQ and HEURSEARCHFREQ.

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 sub-MIP solved by LNS heuristics through the HEURSEARCHEFFORT control, which applies to all enabled LNS heuristics. The default value is 1.0, and increasing it to 2.0 is the equivalent of asking the heuristics to try twice as hard.

Heuristic Controls Summary

HEUREMPHASIS

Select how much emphasis to put on primal heuristics (0 off, 1 emphasis on heuristics or 2 strong emphasis on heuristics).

HEURDIVESTRATEGY

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

HEURFREQ

Run a diving heuristic for every HEURFREQ nodes solved.

HEURSEARCHSTRATEGY

Meta strategy control for all LNS heuristics (-1 automatic, 0 off, 1-3 conservative to aggressive). Overrides the default strategy of individual heuristics that are left at automatic.

HEURSEARCHRINSSTRATEGY, HEURSEARCHLPFIRSTSTRATEGY, HEURSEARCHMIPFIRSTSTRATEGY, HEURSEARCHCOMBINESTRATEGY, HEURSEARCHZEROOBJSTRATEGY, HEURSEARCHANALYTICSTRATEGY

Individual strategy controls for each LNS heuristic (-2 automatic enforced, -1 automatic, 0 off, 1-3 conservative to aggressive). Take precedence over HEURSEARCHSTRATEGY; use -2 to prevent a heuristic's automatic setting being overridden by the meta control. Each of them scales with HEUREMPHASIS.

HEURSEARCHROOTCUTFREQ

How frequently to run LNS heuristics between rounds of root cutting.

HEURSEARCHFREQ

Run LNS heuristics for every HEURSEARCHFREQ nodes solved.

HEURSEARCHEFFORT

Multiplier on the effort spent on LNS heuristics.