Scippy

SCIP

Solving Constraint Integer Programs

How to add presolvers

Presolvers are used to reduce the size of the model by removing irrelevant information like redundant constraints, to strengthen the LP relaxation by exploiting integrality information, and to extract useful information in the presolving step. Constraint based presolving is done in the CONSPRESOL callback methods of the constraint handlers, see CONSPRESOL. Some propagation steps can already be applied in presolving via the PROPRESOL callback methods of propagators, see PROPPRESOL. The presolver plugins complement these by additional, usually optimality based, presolving reductions.
A complete list of all presolvers contained in this release can be found here.

We now explain how users can add their own presolvers. Take the trivial presolver (src/scip/presol_trivial.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::ObjPresol wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_PRESOL... callback methods.

Additional documentation for the callback methods of a presolver, in particular for their input parameters, can be found in the file type_presol.h.

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

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

Properties of a Presolver

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

PRESOL_NAME: the name of the presolver.
This name is used in the interactive shell to address the presolver. Additionally, if you are searching for a presolver with SCIPfindPresol(), this name is looked up. Names have to be unique: no two presolvers may have the same name.
PRESOL_DESC: the description of the presolver.
This string is printed as a description of the presolver in the interactive shell.
PRESOL_TIMING: the default timing of the presolver.
There are three presolving timings: FAST, MEDIUM, and EXHAUSTIVE. Every presolving round starts with the FAST presolvers. MEDIUM presolvers are only called, if FAST presolvers did not find enough reductions in this round so far, and EXHAUSTIVE presolving steps are only performed if all presolvers called before in this round were unsuccessful. Presolvers should be assigned a timing based on how expensive they are, e.g., presolvers that provide fast algorithms that usually have a high impact (i.e., remove lots of variables or tighten bounds of many variables) should have a timing FAST. If a presolver implements different algorithms of different complexity, it may also get multiple timings and check the timing internally in the PRESOLEXEC callback to decide which algorithms to run.
PRESOL_PRIORITY: the priority of the presolver.
Within a presolving round, when calling all presolvers and presolving methods of propagators and constraint handlers with a given timing, those are called in a predefined order, which is given by the priorities of the presolvers and the check priorities of the constraint handlers, see Properties of a Constraint Handler. First, the presolvers with non-negative priority are called in the order of decreasing priority. Next, the presolving methods of the different constraint handlers are called in the order of decreasing check priority. Finally, the presolvers with negative priority are called in the order of decreasing priority.
Again, presolvers that provide fast algorithms that usually have a high impact (i.e., remove lots of variables or tighten bounds of many variables) should have a high priority. An easy way to list the timings and priorities of all presolvers, propagators, and constraint handlers is to type "display presolvers", "display propagators", and "display conshdlrs" in the interactive shell of SCIP.
PRESOL_MAXROUNDS: the default maximal number of rounds the presolver participates in.
The presolving is conducted in rounds: the presolvers and presolving methods of the constraint handlers are called iteratively until no more reductions have been found or some other abort criterion applies. The "maxrounds" parameter of a presolver imposes a limit on the number of presolving rounds in which the presolver is called. The PRESOL_MAXROUNDS property specifies the default value for this parameter. A value of -1 represents an unlimited number of rounds.

Presolver Data

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

Interface Methods

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

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

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

SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );

You also have to initialize the fields in struct SCIP_PresolData afterwards. For freeing the presolver data, see PRESOLFREE.

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

Fundamental Callback Methods of a Presolver

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 presolver itself to SCIP using SCIPincludePresol() or SCIPincludePresolBasic(), see Interface Methods.

Presolver plugins have only one fundamental callback method, namely the PRESOLEXEC method. This method has to be implemented for every presolver; the other callback methods are optional. In the C++ wrapper class scip::ObjPresol, the scip_exec() method (which corresponds to the PRESOLEXEC callback) is a virtual abstract member function. You have to implement it in order to be able to construct an object of your presolver class.

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

PRESOLEXEC

The PRESOLEXEC callback is called inside the presolving loop and should perform the actual presolving reductions. It should inspect the problem instance at hand and simplify it by tightening bounds of variables, aggregating or fixing variables, changing the type of variables, modifying the graph that represents the instance of your application, and the like.

Typical methods called by a presolver are, for example, SCIPchgVarType(), SCIPfixVar(), SCIPaggregateVars(), SCIPtightenVarLb(), and SCIPtightenVarUb().

Additional Callback Methods of a Presolver

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

PRESOLFREE

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

static
SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
{ /*lint --e{715}*/
SCIP_PRESOLDATA* presoldata;
/* free presolver data */
presoldata = SCIPpresolGetData(presol);
assert(presoldata != NULL);
SCIPfreeBlockMemory(scip, &presoldata);
SCIPpresolSetData(presol, NULL);
return SCIP_OKAY;
}

(Source: src/scip/presol_boundshift.c)

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

PRESOLINIT

The PRESOLINIT callback is executed after the problem is transformed. The presolver may, e.g., use this call to initialize its presolver 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).

PRESOLCOPY

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

PRESOLEXIT

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

PRESOLINITPRE

The PRESOLINITPRE callback is executed when the presolving is about to begin. The presolver may use this call to initialize its presolving data which only need to exist during the presolving stage.

PRESOLEXITPRE

The PRESOLEXITPRE callback is executed after presolving finishes and before the branch-and-bound process begins. The presolver should use this call to clean up its presolving data, which was allocated in PRESOLINITPRE.