Scippy

SCIP

Solving Constraint Integer Programs

How to add cut selectors

Cut selectors are used to select the cuts that are going to be added to the relaxation. For more information on how SCIP manages cuts, see "What is the difference between a sepastore and the cutpool?" in the Frequently Asked Questions (FAQ).
A complete list of all cut selectors contained in this release can be found here.

We now explain how users can add their own cut selectors. Take the hybrid cut selector (src/scip/cutsel_hybrid.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::ObjCutsel wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_CUTSEL... callback methods.

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

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

  1. Copy the template files src/scip/cutsel_xyz.c and src/scip/cutsel_xyz.h into files named "cutsel_mycutselector.c" and "cutsel_mycutselector.h".
    Make sure to adjust your build system such that these files are compiled and linked to your project.
    If you are adding a new default plugin, this means updating the src/CMakeLists.txt and Makefile files in the SCIP distribution.
  2. Use SCIPincludeCutselMycutselector() in order to include the cut selector into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
    If you are adding a new default plugin, this include function must be added to src/scipdefplugins.c.
  3. Open the new files with a text editor and replace all occurrences of "xyz" by "mycutselector".
  4. Adjust the properties of the cut selector (see Properties of a Cut Selector).
  5. Define the cut selector data (see Cut 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 Cut Selector).
  8. Implement the additional callback methods (see Additional Callback Methods of a Cut Selector). This is optional.

Properties of a Cut Selector

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

CUTSEL_NAME: the name of the cut selector.
This name is used in the interactive shell to address the cut selector. Additionally, if you are searching for a cut selector with SCIPfindCutsel(), this name is looked up. Names have to be unique: no two cut selectors may have the same name.
CUTSEL_DESC: the description of the cut selector.
This string is printed as a description of the cut selector in the interactive shell.
CUTSEL_PRIORITY: the priority of the cut selector.
After all cuts have been collected in the sepastore, SCIP asks the cut selectors to select cuts. The cut selectors are sorted by priority (highest goes first) and are called, in this order, until the first one succeeds.
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. Whenever, even during solving, the priority of a cut selector is changed, the cut selectors are resorted by the new priorities.

Cut Selector Data

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

Interface Methods

At the bottom of "cutsel_mycutselector.c", you can find the interface method SCIPincludeCutselMycutselector(), which also appears in "cutsel_mycutselector.h" SCIPincludeCutselMycutselector() is called by the user, if they want to include the cut selector, i.e., if they want to use the cut selector in their application.

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the cut selector. For this, you can either call SCIPincludeCutsel() or SCIPincludeCutselBasic(). In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetCutselCopy(). 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 cut selectors in order to compile.

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

SCIP_CALL( SCIPallocBlockMemory(scip, &cutseldata) );

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

You may also add user parameters for your cut selector, see the method SCIPincludeCutselHybrid() in src/scip/cutsel_hybrid.c for an example.

Fundamental Callback Methods of a Cut 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 cut selector itself to SCIP using SCIPincludeCutsel() or SCIPincludeCutselBasic(), see Interface Methods.

Cut selector plugins have a single fundamental callback method, namely the CUTSELSELECT method. This method has to be implemented for every cut selector; the other callback methods are optional. It implements the single contribution every selector has to provide: Selecting cuts to be added to the relaxation. In the C++ wrapper class scip::ObjCutsel, the scip_select() method is a virtual abstract member function. You have to implement it in order to be able to construct an object of your cut selector class.

CUTSELSELECT

The CUTSELSELECT callback should decide which cuts should be added to the relaxation. The callback receives the arrays of cuts to select from. This array must be resorted and the first nselectedcuts from the sorted array are going to be selected. In addition to the aforementioned cuts, the list of forced cuts is also given as an argument. This array can be used to help with the selection algorithm. Note, however, that this array should not be tampered with.

Additional documentation for this callback can be found in type_cutsel.h.

Additional Callback Methods of a Cut 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 SCIPincludeCutsel() to SCIP or via specific setter functions after a call of SCIPincludeCutselBasic(), see also Interface Methods.

CUTSELFREE

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

static
SCIP_DECL_CUTSELFREE(cutselFreeHybrid)
{ /*lint --e{715}*/
SCIP_CUTSELDATA* cutseldata;
cutseldata = SCIPcutselGetData(cutsel);
SCIPfreeBlockMemory(scip, &cutseldata);
return SCIP_OKAY;
}

If you have allocated memory for fields in your cut selector data, remember to free this memory before freeing the cut 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.

CUTSELINIT

The CUTSELINIT callback is executed after the problem is transformed. The cut selector may, for example, use this call to initialize its cut selector data.

CUTSELCOPY

The CUTSELCOPY 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 cut selector for all copied SCIP instances.

CUTSELEXIT

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

CUTSELINITSOL

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

CUTSELEXITSOL

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