SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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.
Every diveset controls the diving behavior through a set of user-defined parameters, which are explained in the following:
Only one callback is necessary to complete a diveset to guide the diving search performed:
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.
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, heuristics.h, and heur_guideddiving.h or other diving heuristics that implement diving through a diveset.