Scippy

SCIP

Solving Constraint Integer Programs

How to add node selectors

Node selectors are used to decide which of the leaves in the current branching tree is selected as next subproblem to be processed. The ordering relation of the tree's leaves for storing them in the leaf priority queue is also defined by the node selectors.
A complete list of all node selectors contained in this release can be found here.

We now explain how users can add their own node selectors. Take the node selector for depth first search (src/scip/nodesel_dfs.c) as an example. As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjNodesel wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_NODESEL... callback methods.

Additional documentation for the callback methods of a node selector can be found in the file type_nodesel.h.

Here is what you have to do to implement a node selector:

  1. Copy the template files src/scip/nodesel_xyz.c and src/scip/nodesel_xyz.h into files named "nodesel_mynodeselector.c" and "nodesel_mynodeselector.h".
    Make sure to adjust your Makefile such that these files are compiled and linked to your project.
  2. Use SCIPincludeNodeselMynodeselector() in oder to include the node selector into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
  3. Open the new files with a text editor and replace all occurrences of "xyz" by "mynodeselector".
  4. Adjust the properties of the node selector (see Properties of a Node Selector).
  5. Define the node selector data (see Node Selector Data). This is optional.
  6. Implement the interface methods (see Interface Methods).
  7. Implement the fundamental callback methods (see Fundamental Callback Methods of a Node Selector).
  8. Implement the additional callback methods (see Additional Callback Methods of a Node Selector). This is optional.

Properties of a Node Selector

At the top of the new file "nodesel_mynodeselector.c" you can find the node selector properties. These are given as compiler defines. In the C++ wrapper class, you have to provide the node selector properties by calling the constructor of the abstract base class scip::ObjNodesel from within your constructor. The properties you have to set have the following meaning:

NODESEL_NAME: the name of the node selector.
This name is used in the interactive shell to address the node selector. Additionally, if you are searching for a node selector with SCIPfindNodesel(), this name is looked up. Names have to be unique: no two node selectors may have the same name.
NODESEL_DESC: the description of the node selector.
This string is printed as a description of the node selector in the interactive shell.
NODESEL_STDPRIORITY: the default priority of the node selector in the standard mode.
The first step of each iteration of the main solving loop is the selection of the next subproblem to be processed. The node selector of highest priority (the active node selector) is called to do this selection. In particular, if you implemented your own node selector plugin which you want to be applied, you should choose a priority which is greater then all priorities of the SCIP default node selectors. Note that SCIP has two different operation modes: the standard mode and the memory saving mode. If the memory limit - given as a parameter by the user - is almost reached, SCIP switches from the standard mode to the memory saving mode in which different priorities for the node selectors are applied. NODESEL_STDPRIORITY is the priority of the node selector used in the standard mode.
Note that this property only defines the default value of the priority. The user may change this value arbitrarily by adjusting the corresponding parameter setting.
NODESEL_MEMSAVEPRIORITY: the default priority of the node selector in the memory saving mode.
The priority NODESEL_MEMSAVEPRIORITY of the node selector has the same meaning as the priority NODESEL_STDPRIORITY, but is used in the memory saving mode. Usually, you want the best performing node selector, for example best estimate search, to have maximal standard priority, while you want a node selector which tends to keep the growth of the search tree limited, for example depth first search, to have maximal memory saving priority.
Note that this property only defines the default value of the priority. The user may change this value arbitrarily by adjusting the corresponding parameter setting.

Node Selector Data

Below the header "Data structures" you can find a struct which is called "struct SCIP_NodeselData". In this data structure, you can store the data of your node selector. For example, you should store the adjustable parameters of the node selector in this data structure. If you are using C++, you can add node selector data as usual as object variables to your class.
Defining node selector data is optional. You can leave the struct empty.

Interface Methods

At the bottom of "nodesel_mynodeselector.c", you can find the interface method SCIPincludeNodeselMynodeselector(), which also appears in "nodesel_mynodeselector.h" SCIPincludeNodeselMynodeselector() is called by the user, if (s)he wants to include the node selector, i.e., if (s)he wants to use the node selector in his/her application.

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the node selector. For this, you can either call SCIPincludeNodesel(), or SCIPincludeNodeselBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetNodeselCopy(). We recommend this latter variant because it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first variant must be manually adjusted with every SCIP release containing new callbacks for node selectors in order to compile.

If you are using node selector data, you have to allocate the memory for the data at this point. You can do this by calling:

SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );

You also have to initialize the fields in struct SCIP_NodeselData afterwards.

You may also add user parameters for your node selector, see the method SCIPincludeNodeselRestartdfs() in src/scip/nodesel_restartdfs.c for an example.

Fundamental Callback Methods of a Node Selector

The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. They are passed together with the node selector itself to SCIP using SCIPincludeNodesel() or SCIPincludeNodeselBasic(), see Interface Methods.

Node selector plugins have two fundamental callback methods, namely the NODESELSELECT method and the NODESELCOMP method. These methods have to be implemented for every node selector; the other callback methods are optional. They implement the two requirements every node selector has to fulfill: Selecting a node from the queue to be processed next and, given two nodes, deciding which of both is favored by the node selector's selection rule. The first task is implemented in the NODESELSELECT callback, the second one in the NODESELCOMP callback. In the C++ wrapper class scip::ObjNodesel, the scip_select() method and the scip_comp() method (which correspond to the NODESELSELECT callback and the NODESELCOMP callback, respectively) are virtual abstract member functions. You have to implement them in order to be able to construct an object of your node selector class.

Additional documentation for the callback methods can be found in type_nodesel.h.

NODESELSELECT

The NODESELSELECT callback is the first method called in each iteration in the main solving loop. It should decide which of the leaves in the current branching tree is selected as the next subproblem to be processed. It can arbitrarily decide between all leaves stored in the tree, but for performance reasons, the current node's children and siblings are often treated different from the remaining leaves. This is mainly due to the warm start capabilities of the simplex algorithm and the expectation that the bases of neighboring vertices in the branching tree very similar. The node selector's choice of the next node to process can have a large impact on the solver's performance, because it influences the finding of feasible solutions and the development of the global dual bound.

Besides the ranking of the node selector, every node gets assigned a node selection priority by the branching rule that created the node. See the BRANCHEXECLP and BRANCHEXECPS callbacks of the branching rules for details. For example, the node where the branching went in the same way as the deviation from the branching variable's root solution could be assigned a higher priority than the node where the branching went in the opposite direction.

The following methods provide access to the various types of leaf nodes:

  • SCIPgetPrioChild() returns the child of the current node with the largest node selection priority, as assigned by the branching rule. If no child is available (for example, because the current node was pruned), a NULL pointer is returned.
  • SCIPgetBestChild() returns the best child of the current node with respect to the node selector's ordering relation as defined by the NODESELCOMP callback. If no child is available, a NULL pointer is returned.
  • SCIPgetPrioSibling() returns the sibling of the current node with the largest node selection priority. If no sibling is available (for example, because all siblings of the current node have already been processed), a NULL pointer is returned. Note that in binary branching every node has at most one sibling, but since SCIP supports arbitrary branching rules, this might not always be the case.
  • SCIPgetBestSibling() returns the best sibling of the current node with respect to the node selector's ordering relation as defined by the NODESELCOMP callback. If no sibling is available, a NULL pointer is returned.
  • SCIPgetBestNode() returns the best leaf from the tree (children, siblings, or other leaves) with respect to the node selector's ordering relation as defined by the NODESELCOMP callback. If no open leaf exists, a NULL pointer is returned. In this case, the optimization is finished, and the node selector should return a NULL pointer as 'selnode'.
  • SCIPgetBestboundNode() returns a leaf from the tree (children, siblings, or other leaves) with the smallest lower (dual) objective bound. If the queue is empty, a NULL pointer is returned. In this case, the optimization is finished, and the node selector should return a NULL pointer as 'selnode'.

NODESELCOMP

The NODESELCOMP callback is called to compare two leaves of the current branching tree (say node 1 and node 2) regarding their ordering relation.

The NODESELCOMP should return the following values:

  • value < 0, if node 1 comes before (is better than) node 2
  • value = 0, if both nodes are equally good
  • value > 0, if node 1 comes after (is worse than) node 2.

Additional Callback Methods of a Node Selector

The additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications, they can be used, for example, to initialize and free private data. Additional callbacks can either be passed directly with SCIPincludeNodesel() to SCIP or via specific setter functions after a call of SCIPincludeNodeselBasic(), see also Interface Methods.

NODESELFREE

If you are using node selector data, you have to implement this method in order to free the node selector data. This can be done by the following procedure:

static
SCIP_DECL_NODESELFREE(nodeselFreeBfs)
{ /*lint --e{715}*/
SCIP_NODESELDATA* nodeseldata;
assert(nodesel != NULL);
assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
assert(scip != NULL);
/* free user data of node selector */
nodeseldata = SCIPnodeselGetData(nodesel);
assert(nodeseldata != NULL);
SCIPfreeBlockMemory(scip, &nodeseldata);
SCIPnodeselSetData(nodesel, nodeseldata);
return SCIP_OKAY;
}

(Source: src/scip/nodesel_bfs.c)

If you have allocated memory for fields in your node selector data, remember to free this memory before freeing the node selector data itself. If you are using the C++ wrapper class, this method is not available. Instead, just use the destructor of your class to free the member variables of your class.

NODESELINIT

The NODESELINIT callback is executed after the problem is transformed. The node selector may, e.g., use this call to initialize its node selector data.

NODESELCOPY

The NODESELCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as NULL the user disables the execution of the specified node selector for all copied SCIP instances. This may deteriorate the performance of primal heuristics using sub-SCIPs.

NODESELEXIT

The NODESELEXIT callback is executed before the transformed problem is freed. In this method, the node selector should free all resources that have been allocated for the solving process in NODESELINIT.

NODESELINITSOL

The NODESELINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin. The node selector may use this call to initialize its branch-and-bound specific data.

NODESELEXITSOL

The NODESELEXITSOL callback is executed before the branch-and-bound process is freed. The node selector should use this call to clean up its branch-and-bound data.