How to implement a diving heuristic

Diving heuristics are an important addon to the branch-and-cut search. A diving heuristic explores a single probing path down the search tree. In contrast to the regular search guided by branching rule(s) and the selected node selector, the diving is performed in an auxiliary tree originating from the focus node of the main search tree where the heuristic was called. The advantage of this approach is that many different scoring mechanisms can be safely tried as diving heuristic and may probably lead to better solutions. SCIP has a lot of diving heuristics included in its default plugin set.
Since SCIP version 3.2, the diving heuristics have been redesigned to contain mainly the scoring function used by the heuristic. In order to implement a user-defined diving heuristic, it is possible to create one (or several) divesets that control the scoring mechanism and add them to the primal heuristic. This has the advantage that less code is necessary to create a working diving heuristic. The SCIP statistics now also display some interesting statistics about every diveset together in the section 'Diving Statistics'.
This page contains the necessary steps to understand and include a diveset into ones primal diving heuristic plugin. As a prerequisite, you should understand the basic implementation steps for a primal heuristic, see How to add primal heuristics. In order to make use of divesets, they must be included after the primal heuristic to which they should belong has been included, by using SCIPincludeDiveset(). This will create the data structure for the diveset and append it to the list of divesets belonging to the heuristic, which can be retrieved later together with their number by using SCIPheurGetDivesets() and SCIPheurGetNDivesets(), respectively. No further memory allocation or deletion is needed; As a member of the heuristic, SCIP automatically takes care of freeing the diveset when it is exiting.
Before the inclusion, one may think of adjusting the various properties that a diveset offers to control the behavior of the algorithm. These are subject to the following section.
It is mandatory to implement the fundamental scoring callback of the diveset, which is explained in more detail in Section Fundamental callbacks of a diveset.
Once the properties have been carefully adjusted and the scoring has been defined, use the method SCIPperformGenericDivingAlgorithm() inside the execution callback (HEUREXEC) of the primal heuristic to which the diveset belongs, after checking possible preliminaries that may not be met at all times of the search.
For a code example, we refer to heur_guideddiving.h, which guides the diving into the direction of the current incumbent solution. Before it calls SCIPperformGenericDivingAlgorithm(), it checks whether an incumbent is available, and returns if there is none.

User parameters and properties for every diveset

Every diveset controls the diving behavior through a set of user-defined parameters, which are explained in the following:

MINRELDEPTH

the minimal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving

MAXRELDEPTH

the maximal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving

MAXLPITERQUOT

maximal fraction of diving LP iterations compared to node LP iterations that this dive controller may consume

MAXLPITEROFS

an additional number of allowed LP iterations

MAXDIVEUBQUOT

maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)

MAXDIVEAVGQUOT

maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)

MAXDIVEUBQUOTNOSOL

maximal UBQUOT when no solution was found yet (0.0: no limit)

MAXDIVEAVGQUOTNOSOL

maximal AVGQUOT when no solution was found yet (0.0: no limit)

BACKTRACK

use one level of backtracking if infeasibility is encountered?

LPRESOLVEDOMCHGQUOT

parameter to control LP resolve dynamically based on this percentage of observed bound changes relative to all variables or the LP branching candidates (integer variables with fractional solution values) from the last node where an LP has been solved. This property has no effect when the LPSOLVEFREQ is set to 1.

LPSOLVEFREQ

LP solve frequency for diveset, use a positive integer k to solve an LP at every k'th depth of the diving search (ie. 1 causes the diveset to solve all intermediate LPs) or 0 to only resolve the LP relaxation after propagation found at least a certain percentage domain changes, see also the previous LPRESOLVEDOMCHGQUOT parameter.

ONLYLPBRANCHCANDS

Set this property to TRUE if only LP branching candidates be considered for the execution of the diving algorithm instead of the slower but more general constraint handler diving variable selection.

DIVETYPES

bit mask that represents all supported dive types. Irrelevant if only LP branching candidates should be scored, otherwise, different constraint handlers may ask the diveset if it supports their preferred divetype. See type_heur.h for a list of available dive types.

Fundamental callbacks of a diveset

Only one callback is necessary to complete a diveset to guide the diving search performed:

DIVESETGETSCORE

The scoring callback expects a candidate variable and calculates a score value and a preferred direction. The selected variable for diving will be one that maximizes the score function provided by the diveset. If the diveset should support more than one possible type of diving, it may use the divetype argument as a hint how the caller of the score function (could be the diving algorithm itself or one of the constraint handlers that implement diving variable selection) intends to perform the search.

Further information

This is all there is to extend the SCIP set of diving heuristics by a new one. For further information, please see diveset related methods in type_heur.h, pub_heur.h, pub_dive.h, and heur_guideddiving.h or other diving heuristics that implement diving through a diveset.