How to add propagators

Propagators are used to tighten the domains of the variables. Like for cutting planes, there are two different types of domain propagations. Constraint based (primal) domain propagation algorithms are part of the corresponding constraint handlers, see CONSPROP. In contrast, domain propagators usually provide dual propagations, i.e., propagations that can be applied using the objective function and the current best known primal solution. This section deals with such propagators.

A complete list of all propagators contained in this release can be found here.

We now explain how users can add their own propagators. Take the pseudo objective function propagator (src/scip/prop_pseudoobj.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::ObjProp wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_PROP... callback methods.

Additional documentation for the callback methods of a propagator can be found in the file type_prop.h.

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

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

Properties of a Propagator

At the top of the new file "prop_mypropagator.c" you can find the propagator properties. These are given as compiler defines. The presolving-related properties are optional, they only have to be defined if the propagator supports presolving routines. In the C++ wrapper class, you have to provide the propagator properties by calling the constructor of the abstract base class scip::ObjProp from within your constructor. The properties you have the following meaning:

Fundamental properties of a propagator

PROP_NAME: the name of the propagator.

This name is used in the interactive shell to address the propagator. Additionally, if you are searching for a propagator with SCIPfindProp(), this name is searched for. Names have to be unique: no two propagators may have the same name.

PROP_DESC: the description of the propagator.

This string is printed as a description of the propagator in the interactive shell.

PROP_PRIORITY: the priority of the propagator.

In each propagation round, the propagators and propagation methods of the constraint handlers are called in a predefined order, which is given by the priorities of the propagators and the check priorities of the constraint handlers. First, the propagators with non-negative priority are called in order of decreasing priority. Next, the propagation methods of the different constraint handlers are called in order of decreasing check priority. Finally, the propagators with negative priority are called in order of decreasing priority.
The priority of the propagators should be set according to the complexity of the propagation algorithm and the impact of the domain propagations: propagators providing fast algorithms that usually have a high impact (i.e., tighten many bounds) should have a high priority.

PROP_FREQ: the default frequency for propagating domains.

The frequency defines the depth levels at which the propagation method PROPEXEC is called. For example, a frequency of 7 means, that the propagation callback is executed for subproblems that are in depth 0, 7, 14, ... of the branching tree. A frequency of 0 means that propagation is only applied in preprocessing and at the root node. A frequency of -1 disables the propagator.
The frequency can be adjusted by the user. This property of the propagator only defines the default value of the frequency.
Note: If you want to have a more flexible control of when to execute the propagation algorithm, you have to assign a frequency of 1 and implement a check at the beginning of your propagation algorithm whether you really want to execute the domain propagation or not. If you do not want to execute it, set the result code to SCIP_DIDNOTRUN.

PROP_DELAY: the default for whether the propagation method should be delayed, if other propagators or constraint handlers found domain reductions.

If the propagator's propagation method is marked to be delayed, it is only executed after no other propagator or constraint handler found a domain reduction in the current iteration of the domain propagation loop. If the propagation method of the propagator is very expensive, you may want to mark it to be delayed until all cheap propagation methods have been executed.

PROP_TIMING: the timing mask of the propagator.

SCIP calls the domain propagation routines at different places in the node processing loop. This property indicates at which places the propagator is called. Possible values are defined in type_timing.h and can be concatenated, e.g., as in SCIP_PROPTIMING_ALWAYS.

Optional propagator properties

The following properties are optional and only need to be defined if the propagator supports presolving, that is, if the presolving callback is implemented.

PROP_PRESOLTIMING: the timing of the presolving method (FAST, MEDIUM, or EXHAUSTIVE).

Every presolving round starts with the FAST presolving methods. 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. Presolving methods 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 presolving method implements different algorithms of different complexity, it may also get multiple timings and check the timing internally in the PROPPRESOL callback to decide which algorithms to run.

PROP_PRESOL_PRIORITY: the priority of the presolving method.

This attribute is analogous to the PROP_PRIORITY flag, but deals with the preprocessing method of the presolver.

PROP_PRESOL_MAXROUNDS: the default maximal number of presolving rounds the propagator participates in.

The preprocessing is executed in rounds. If enough changes have been applied to the model, an additional preprocessing round is performed. The MAXROUNDS parameter of a propagator denotes the maximal number of preprocessing rounds, the propagator participates in. A value of -1 means, that there is no limit on the number of rounds. A value of 0 means, the preprocessing callback of the propagator is disabled.

Propagator Data

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

Interface Methods

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

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the propagator. For this, you can either call SCIPincludeProp(), or SCIPincludePropBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetPropCopy(). 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 propagator data, you have to allocate the memory for the data at this point. You can do this by calling

SCIP_CALL( SCIPallocMemory(scip, &propdata) );

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

You may also add user parameters for your propagator, see the method SCIPincludePropPseudoobj() in src/scip/prop_pseudoobj.c for an example.

Fundamental Callback Methods of a Propagator

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 propagator itself to SCIP using SCIPincludeProp() or SCIPincludePropBasic(), see Interface Methods.

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

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

PROPEXEC

The PROPEXEC callback is called during presolving and during the subproblem processing. It should perform the actual domain propagation, which means that it should tighten the variables' bounds. The technique of domain propagation, which is the main workhorse of constraint programming, is called "node preprocessing" in the Integer Programming community.

The PROPEXEC callback has the following options:

• detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
• reducing (i.e, tightening) the domains of some variables (result SCIP_REDUCEDDOM)
• stating that the propagator searched, but did not find domain reductions, cutting planes, or cut constraints (result SCIP_DIDNOTFIND)
• stating that the propagator was skipped (result SCIP_DIDNOTRUN)
• stating that the propagator was skipped, but should be called again (result SCIP_DELAYED)

Additional Callback Methods of a Propagator

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

PROPRESPROP

If the propagator wants to support conflict analysis, it has to supply the PROPRESPROP method. It also should call SCIPinferVarLbProp() or SCIPinferVarUbProp() in the domain propagation instead of SCIPchgVarLb() or SCIPchgVarUb() in order to deduce bound changes on variables. In the SCIPinferVarLbProp() and SCIPinferVarUbProp() calls, the propagator provides a pointer to itself and an integer value "inferinfo" that can be arbitrarily chosen.

The propagation conflict resolving method PROPRESPROP must then be implemented to provide the "reasons" for the bound changes, i.e., the bounds of variables at the time of the propagation, which forced the propagator to set the conflict variable's bound to its current value. It can use the "inferinfo" tag to identify its own propagation rule and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided by calls to SCIPaddConflictLb() and SCIPaddConflictUb() in the propagation conflict resolving method.

See the description of the propagation conflict resolving method CONSRESPROP of constraint handlers for further details.

Omitting the PROPRESPROP callback circumvents the implementation of the usually rather complex conflict resolving method. Yet, it will make the conflict analysis less effective. We suggest to first omit the conflict resolving method and check how effective the propagation method is. If it produces a lot of propagations for your application, you definitely should consider implementing the conflict resolving method.

PROPFREE

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

static
SCIP_DECL_PROPFREE(propFreeMypropagator)
{
   SCIP_PROPDATA* propdata;

   propdata = SCIPpropGetData(prop);
   assert(propdata != NULL);

   SCIPfreeMemory(scip, &propdata);

   SCIPpropSetData(prop, NULL);

   return SCIP_OKAY;
}

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

PROPINIT

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

PROPCOPY

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

PROPEXIT

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

PROPINITPRE

The PROPINITPRE callback is executed before the preprocessing is started, even if presolving is turned off. The propagator may use this call to initialize its presolving data before the presolving process begins.

PROPEXITPRE

The PROPEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off. The propagator may use this call, e.g., to clean up its presolving data. Besides clean up, no time consuming operations should be done.

PROPINITSOL

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

PROPEXITSOL

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

PROPPRESOL

Seaches for domain propagations, analogous to the PROPEXEC callback. However, this callback is called during preprocessing.

To inform SCIP that the presolving method found a reduction the result pointer has to be set in a proper way. The following options are possible:

• SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in objective direction
• SCIP_CUTOFF : at least one domain reduction that renders the problem infeasible has been found
• SCIP_SUCCESS : the presolver found a domain reduction
• SCIP_DIDNOTFIND : the presolver searched, but did not find a presolving change
• SCIP_DIDNOTRUN : the presolver was skipped
• SCIP_DELAYED : the presolver was skipped, but should be called again

Please see also the Optional propagator properties section to learn about the properties PROP_PRESOLTIMING and PROP_PRESOL_MAXROUNDS, which influence the behaviour of SCIP calling PROPPRESOL.