Scippy

SCIP

Solving Constraint Integer Programs

How to add separators

Separators are used to generate general purpose cutting planes. Constraint based cutting planes, the second type of cutting planes in SCIP, are separated in the CONSSEPALP and CONSSEPASOL callback methods of the constraint handlers, see CONSSEPALP and CONSSEPASOL. These cuts are valid inequalities or even facets of the polyhedron described by a single constraint or a subset of the constraints of a single constraint class. In contrast, general purpose cuts do not require or exploit any knowledge about the underlying problem structure but use only the current LP relaxation and the integrality conditions. See also "When should I implement a constraint handler, when should I implement a separator?" on Frequently Asked Questions (FAQ).
A complete list of all separators contained in this release can be found here.

We now explain how users can add their own separators. Take the separator for the class of Gomory mixed integer inequalities (src/scip/sepa_gomory.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::ObjSepa wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_SEPA... callback methods.

Additional documentation for the callback methods of a separator, in particular for the input parameters, can be found in the file type_sepa.h.

Here is what you have to do to implement a separator:

  1. Copy the template files src/scip/sepa_xyz.c and src/scip/sepa_xyz.h into files "sepa_myseparator.c" and "sepa_myseparator.h".
    Make sure to adjust your Makefile such that these files are compiled and linked to your project.
  2. Use SCIPincludeSepaMyseparator() in order to include the separator 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 "myseparator".
  4. Adjust the properties of the separator (see Properties of a Separator).
  5. Define the separator data (see Separator Data). This is optional.
  6. Implement the interface methods (see Interface Methods).
  7. Implement the fundamental callback methods (see Fundamental Callback Methods of a Separator).
  8. Implement the additional callback methods (see Additional Callback Methods of a Separator). This is optional.

Properties of a Separator

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

SEPA_NAME: the name of the separator.
This name is used in the interactive shell to address the separator. Additionally, if you are searching for a separator with SCIPfindSepa(), this name is looked up. Names have to be unique: no two separators may have the same name.
SEPA_DESC: the description of the separator.
This string is printed as a description of the separator in the interactive shell.
SEPA_PRIORITY: the priority of the separator.
In each separation round during the price-and-cut loop of the subproblem processing or the separation loop of the primal solution separation, the separators and separation methods of the constraint handlers are called in a predefined order, which is given by the priorities of the separators and the separation priorities of the constraint handlers (see Properties of a Constraint Handler). First, the separators with non-negative priority are called in the order of decreasing priority. Next, the separation methods of the constraint handlers are called in the order of decreasing separation priority. Finally, the separators with negative priority are called in the order of decreasing priority. An easy way to list the priorities of all separators and constraint handlers is to type "display separators" and "display conshdlrs" in the interactive shell.
The priority of the separator should be set according to the complexity of the cut separation algorithm and the impact of the resulting cuts: separators that provide fast algorithms that usually have a high impact (i.e., cut off a large portion of the LP relaxation) should have a high priority. See SEPAEXECLP and SEPAEXECSOL for further details of the separation callbacks.
SEPA_FREQ: the default frequency for separating cuts.
The frequency defines the depth levels at which the separation methods SEPAEXECLP and SEPAEXECSOL are called. For example, a frequency of 7 means, that the separation callback is executed for subproblems that are in depth 0, 7, 14, ... of the branching tree. A frequency of 0 means, that the separation method is only called at the root node. A frequency of -1 disables the separator.
The frequency can be adjusted by the user. This property of the separator only defines the default value of the frequency. If you want to have a more flexible control of when to execute the separation algorithm, you have to assign a frequency of 1 and implement a check at the beginning of your separation methods whether you really want to execute the separation or not. If you do not want to execute it, set the result code of SEPAEXECLP and SEPAEXECSOL to SCIP_DIDNOTRUN.
SEPA_MAXBOUNDDIST: the default maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.
At the current branch-and-bound node, the relative distance from its dual bound (local dual bound) to the primal bound compared to the best node's dual bound (global dual bound) is considered. The separation method of the separator will only be applied at the current node if this relative distance does not exceed SEPA_MAXBOUNDDIST.
For example, if the global dual bound is 50 and the primal bound is 60, SEPA_MAXBOUNDDIST = 0.25 means that separation is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it is less than or equal to 52.5.
In particular, the values 0.0 and 1.0 mean that separation is applied at the current best node only or at all nodes, respectively. Since separation seems to be most important to apply at nodes that define to the global dual bound, 0.0 is probably a good choice for SEPA_MAXBOUNDDIST. Note that separators with a frequency of SEPA_FREQ = 0 are only applied at the root node. Obviously, at the root node the local dual bound is equal to the global dual bound and thus, the separator is called for any value of SEPA_MAXBOUNDDIST.
SEPA_USESSUBSCIP: Does the separator use a secondary SCIP instance?
Some heuristics and separators solve MIPs or SAT problems and use a secondary SCIP instance. Examples are Large Neighborhood Search heuristics such as RINS and Local Branching or the CGMIP separator. To avoid recursion, these plugins usually deactivate all other plugins that solve MIPs. If a separator uses a secondary SCIP instance, this parameter has to be TRUE and it is recommended to call SCIPsetSubscipsOff() for the secondary SCIP instance.
SEPA_DELAY: the default for whether the separation method should be delayed, if other separators or constraint handlers found cuts.
If the separator's separation method is marked to be delayed, it is only executed after no other separator or constraint handler found a cut during the price-and-cut loop. If the separation method of the separator is very expensive, you may want to mark it to be delayed until all cheap separation methods have been executed.

Separator Data

Below the header "Data structures" you can find a struct which is called "struct SCIP_SepaData". In this data structure, you can store the data of your separator. For example, you should store the adjustable parameters of the separator in this data structure. In a separator, user parameters for the maximal number of separation rounds per node and for the maximal number of cuts separated per separation round might be useful. If you are using C++, you can add separator data as usual as object variables to your class.
Defining separator data is optional. You can leave the struct empty.

Interface Methods

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

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the separator. For this, you can either call SCIPincludeSepa(), or SCIPincludeSepaBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetSepaCopy(). 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 separators in order to compile.

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

SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );

You also have to initialize the fields in "struct SCIP_SepaData" afterwards. For freeing the separator data, see SEPAFREE.

You may also add user parameters for your separator, see How to add additional user parameters for how to add user parameters and the method SCIPincludeSepaGomory() in src/scip/sepa_gomory.c for an example.

Fundamental Callback Methods of a Separator

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 separator itself to SCIP using SCIPincludeSepa() or SCIPincludeSepaBasic(), see Interface Methods.

Separator plugins have two callbacks, SEPAEXECLP and SEPAEXECSOL, of which at least one must be implemented.

Additional documentation for the callback methods, in particular to their input parameters, can be found in type_sepa.h.

SEPAEXECLP

The SEPAEXECLP callback is executed during the price-and-cut loop of the subproblem processing. It should try to generate general purpose cutting planes in order to separate the current LP solution. The method is called in the LP solution loop, which means that a valid LP solution exists.

Usually, the callback searches and produces cuts, that are added with a call to SCIPaddCut(). If the cut should be added to the global cut pool, it calls SCIPaddPoolCut(). In addition to LP rows, the callback may also produce domain reductions or add additional constraints.

Overall, the SEPAEXECLP callback has the following options, which is indicated by the possible return values of the 'result' variable (see type_sepa.h):

  • detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
  • adding an additional constraint (result SCIP_CONSADDED)
  • reducing a variable's domain (result SCIP_REDUCEDDOM)
  • adding a cutting plane to the LP (result SCIP_SEPARATED)
  • stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints (result SCIP_DIDNOTFIND)
  • stating that the separator was skipped (result SCIP_DIDNOTRUN)
  • stating that the separator was skipped, but should be called again (result SCIP_DELAYED)
  • stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)

SEPAEXECSOL

The SEPAEXECSOL callback is executed during the separation loop on arbitrary primal solutions. It should try to generate general purpose cutting planes in order to separate the given primal solution. The method is not called in the LP solution loop, which means that there is no valid LP solution.

In the standard SCIP environment, the SEPAEXECSOL callback is not used because only LP solutions are separated. The SEPAEXECSOL callback provides means to support external relaxation handlers like semidefinite relaxations that want to separate an intermediate primal solution vector. Thus, if you do not want to support such external plugins, you do not need to implement this callback method.

Usually, the callback searches and produces cuts, that are added with a call to SCIPaddCut(). If the cut should be added to the global cut pool, it calls SCIPaddPoolCut(). In addition to LP rows, the callback may also produce domain reductions or add other constraints.

Overall, the SEPAEXECSOL callback has the following options, which is indicated by the possible return values of the 'result' variable (see type_sepa.h):

  • detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
  • adding an additional constraint (result SCIP_CONSADDED)
  • reducing a variable's domain (result SCIP_REDUCEDDOM)
  • adding a cutting plane to the LP (result SCIP_SEPARATED)
  • stating that the separator searched, but did not find domain reductions, cutting planes, or cut constraints (result SCIP_DIDNOTFIND)
  • stating that the separator was skipped (result SCIP_DIDNOTRUN)
  • stating that the separator was skipped, but should be called again (result SCIP_DELAYED)
  • stating that a new separation round should be started without calling the remaining separator methods (result SCIP_NEWROUND)

Additional Callback Methods of a Separator

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 SCIPincludeSepa() to SCIP or via specific setter functions after a call of SCIPincludeSepaBasic(), see also Interface Methods.

SEPAFREE

If you are using separator data (see Separator Data and Interface Methods), you have to implement this method in order to free the separator data. This can be done by the following procedure:

static
SCIP_DECL_SEPAFREE(sepaFreeGomory)
{ /*lint --e{715}*/
SCIP_SEPADATA* sepadata;
assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
/* free separator data */
sepadata = SCIPsepaGetData(sepa);
assert(sepadata != NULL);
/* free random number generator */
SCIPrandomFree(&sepadata->randnumgen);
SCIPfreeBlockMemory(scip, &sepadata);
SCIPsepaSetData(sepa, NULL);
return SCIP_OKAY;
}

(Source: src/scip/sepa_gomory.c)

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

SEPACOPY

The SEPACOPY 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 separator for all copied SCIP instances. This may deteriorate the performance of primal heuristics using sub-SCIPs.

SEPAINIT

The SEPAINIT callback is executed after the problem is transformed. The separator may, e.g., use this call to initialize its separator data. The difference between the original and the transformed problem is explained in "What is this thing with the original and the transformed problem about?" on Frequently Asked Questions (FAQ).

SEPAEXIT

The SEPAEXIT callback is executed before the transformed problem is freed. In this method, the separator should free all resources that have been allocated for the solving process in SEPAINIT.

SEPAINITSOL

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

SEPAEXITSOL

The SEPAEXITSOL callback is executed before the branch-and-bound process is freed. The separator should use this call to clean up its branch-and-bound data, in particular to release all LP rows that it has created or captured.