How to add constraint handlers

A constraint handler defines the semantics and the algorithms to process constraints of a certain class. A single constraint handler is responsible for all constraints belonging to its constraint class. For example, there is one knapsack constraint handler that ensures solutions are only accepted if they satisfy all knapsack constraints in the model.
A complete list of all constraint handlers contained in this release can be found here.

We now explain how users can add their own constraint handlers. For an example, look into the subtour constraint handler (examples/TSP/src/ConshdlrSubtour.cpp) of the Traveling Salesman Problem project. The example is written in C++ and uses the C++ wrapper classes. However, we will explain the implementation of a constraint handler using the C interface. It is very easy to transfer the C explanation to C++; whenever a method should be implemented using the SCIP_DECL_CONS... notion, reimplement the corresponding virtual member function of the abstract scip::ObjConshdlr base class.

Additional documentation for the callback methods of a constraint handler can be found in the file type_cons.h.

Here is what you have to do (assuming your constraint handler should be named "subtour"):

1. Copy the template files src/scip/cons_xyz.c and src/scip/cons_xyz.h into files "cons_subtour.c" and "cons_subtour.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 SCIPincludeConshdlrSubtour() in order to include the constraint handler into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cppmain.cpp in the TSP 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 "subtour".
4. Adjust the properties of the constraint handler.
5. Define the constraint data and the constraint handler data. This is optional.
6. Implement the interface methods.
7. Implement the fundamental callback methods.
8. Implement the additional callback methods. This is optional.

Properties of a Constraint Handler

At the top of the new file "cons_subtour.c" you can find the constraint handler properties. These are given as compiler defines. Some of them are optional, as, e.g., separation-related properties, which only have to be defined if the constraint handler supports the related callbacks. In the C++ wrapper class, you have to provide the constraint handler properties by calling the constructor of the abstract base class scip::ObjConshdlr from within your constructor (see the TSP example). The properties you have to set have the following meaning:

Fundamental Constraint Handler properties

CONSHDLR_NAME: the name of the constraint handler.

This name is used in the interactive shell to address the constraint handler. Additionally, if you are searching for a constraint handler with SCIPfindConshdlr(), this name is looked up. Names have to be unique: no two constraint handlers may have the same name.

CONSHDLR_DESC: the description of the constraint handler.

This string is printed as a description of the constraint handler in the interactive shell of SCIP.

CONSHDLR_ENFOPRIORITY: the priority of the constraint handler for constraint enforcing.

Like the separation priority, the enforcement priorities define the order in which the different constraint handlers are called in the constraint enforcement step of the subproblem processing. The constraint enforcement is called after the price-and-cut loop is executed (in the case that the LP is solved at the current subproblem).
The integrality constraint handler has an enforcement priority of 0. That means, if a constraint handler has negative enforcement priority, it only has to deal with integral solutions in its enforcement methods, because for fractional solutions, the integrality constraint handler would have created a branching, thereby aborting the enforcement step. If you want to implement a constraint-depending branching rule (for example, SOS branching on special ordered set constraints), you have to assign a positive enforcement priority to your constraint handler. In this case, you have to be able to deal with fractional solutions.
See CONSENFOLP and CONSENFOPS for further details of the separation callback.

CONSHDLR_CHECKPRIORITY: the priority of the constraint handler for checking feasibility.

Like the separation priority, the checking priorities define the order in which the different constraint handlers are called to check the feasibility of a given primal solution candidate. The integrality constraint handler has a checking priority of 0. That means, constraint handlers with negative checking priorities only have to deal with integral solutions.

CONSHDLR_EAGERFREQ: the default frequency for using all instead of only the useful constraints in separation, propagation and enforcement.

If constraint aging is activated, some constraints that were not useful in the past for propagation or separation are marked to be obsolete. Usually, the obsolete constraints are not presented to the separation and propagation methods of the constraint handlers, such that the constraint handlers only process the non-obsolete constraints. However, every n'th call, with n being the EAGERFREQ of the constraint handler, all constraints are presented to the separation and propagation methods of the constraint handler. This gives obsolete constraints the chance of becoming non-obsolete again.
If the eager evaluation frequency is set to -1, obsolete constraints are never presented to the separation and propagation methods. A frequency of 0 means, that obsolete constraints are only used in the first call of each method.

CONSHDLR_NEEDSCONS: indicates whether the constraint handler should be skipped, if no constraints are available.

Usually, a constraint handler is only executed if there are constraints of its corresponding class in the model. For those constraint handlers, the NEEDSCONS flag should be set to TRUE. However, some constraint handlers must be called without having a constraint of the class in the model, because the constraint is only implicitly available. For example, the integrality constraint handler has the NEEDSCONS flag set to FALSE, because there is no explicit integrality constraint in the model. The integrality conditions are attached to the variables, and the integrality constraint handler has to check all variables that are marked to be integer for integral values.

Optional Constraint Handler properties

The following properties are optional and only need to be defined if the constraint handlers support separation, presolving, propagation, and/or upgrade functionality.

LINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of linear constraints

This property is only needed if a certain linear constraint can be upgraded to a more specific one. In one of the first presolving rounds SCIP tries to upgrade linear constraints to more specialized constraints, such as knapsack constraints. The upgrading calls are processed in the order of decreasing priority.

NONLINCONSUPGD_PRIORITY: priority of the constraint handler for upgrading of nonlinear constraints

This property has the same effect as the LINCONSUPGD_PRIORITY parameter, see above, and should be set whenever an upgrade functionality from a general nonlinear constraint to the more specific one is defined.

CONSHDLR_SEPAFREQ: the default frequency for separating cuts.

The separation frequency defines the depth levels at which the constraint handler's separation methods CONSSEPALP and CONSSEPASOL are called. For example, a separation frequency of 7 means, that the separation callback is executed for subproblems that are in depth 0, 7, 14, ... of the branching tree. A separation frequency of 0 means, that the separation method is only called at the root node. A separation frequency of -1 disables the separation method of the constraint handler.
The separation frequency can be adjusted by the user. This property of the constraint handler 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 separation frequency of 1 and implement a check at the beginning of your separation algorithm whether you really want to execute the separator or not. If you do not want to execute the method, set the result code to SCIP_DIDNOTRUN.

CONSHDLR_SEPAPRIORITY: the priority of the constraint handler for separation. (optional: to be set only if the constraint handler supports separation)

In each separation round during the price-and-cut loop of the subproblem processing or during 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. First, the separators with non-negative priority are called in the order of decreasing priority. Next, the separation methods of the different 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.
The separation priority of the constraint handler should be set according to the complexity of the cut separation algorithm and the impact of the resulting cuts: Constraint handlers 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 CONSSEPALP and CONSSEPASOL for further details of the separation callbacks.

CONSHDLR_DELAYSEPA: the default for whether the separation method should be delayed, if other separators found cuts.

If the constraint handler'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 constraint handler is very expensive, you may want to mark it to be delayed until all cheap separation methods have been executed.

CONSHDLR_PROPFREQ: the default frequency for propagating domains.

This default frequency has the same meaning as the CONSHDLR_SEPAFREQ with respect to the domain propagation callback of the constraint handler. A propagation frequency of 0 means that propagation is only applied in preprocessing and at the root node. A propagation frequency of -1 disables the propagation method of the constraint handler.

CONSHDLR_DELAYPROP: the default for whether the propagation method should be delayed, if other propagators found reductions.

This property is analogous to the DELAYSEPA flag, but deals with the propagation method of the constraint handler.

CONSHDLR_PROP_TIMING: the propagation timing mask of the constraint handler.

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

CONSHDLR_PRESOLTIMING: the timing of the constraint handler's 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 CONSPRESOL callback to decide which algorithms to run.

CONSHDLR_MAXPREROUNDS: the default maximal number of presolving rounds the constraint handler participates in.

The preprocessing is executed in rounds. If enough changes have been applied to the model, an additional preprocessing round is performed. The MAXPREROUNDS parameter of a constraint handler denotes the maximal number of preprocessing rounds the constraint handler 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 constraint handler is disabled.

Constraint Data and Constraint Handler Data

Below the header "Data structures" you can find two structs called "struct SCIP_ConsData" and "struct SCIP_ConshdlrData". If you are using C++, you only need to define the "struct SCIP_ConsData". The constraint handler data must be implemented as member variables of your constraint handler class.
The constraint data are the information that is needed to define a single constraint of the constraint handler's constraint class. For example, the data of a knapsack constraint would consist of a list of variables, a list of weights, and the capacity of the knapsack. The data of a subtour constraint consists of the graph on which the problem is defined. In the graph, each edge should be linked to the corresponding binary problem variable.
The constraint handler data are additional variables, that belong to the constraint handler itself and which are not specific to a single constraint. For example, you can use these data to store parameters of the constraint handler or statistical information. The constraint handler data are optional. You can leave the struct empty.

Interface Methods

At the bottom of "cons_subtour.c" you can find three interface methods, that also appear in "cons_subtour.h". These are SCIPincludeConshdlrSubtour(), SCIPcreateConsSubtour(), and SCIPcreateConsSubtourBasic().
The method SCIPincludeConshdlrSubtour() only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the constraint handler by calling the method SCIPincludeConshdlr(). It is called by the user, if (s)he wants to include the constraint handler, i.e., if (s)he wants to make the constraint handler available to the model, and looks like this:

1. If you are using constraint handler data, you have to allocate the memory for the data at this point. You also have to initialize the fields in struct SCIP_ConshdlrData afterwards.

   SCIP_RETCODE SCIPincludeConshdlrKnapsack(
      SCIP*                 scip                /**< SCIP data structure */
      )
   {
      SCIP_EVENTHDLRDATA* eventhdlrdata;
      SCIP_CONSHDLRDATA* conshdlrdata;
      SCIP_CONSHDLR* conshdlr;
   
      /* create knapsack constraint handler data */
      SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );

2. Now, SCIP gets notified of the presence of the constraint handler together with its basic callbacks.

      SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
            CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
            consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
            conshdlrdata) );
   
      assert(conshdlr != NULL);

3. All additional callbacks are added via their setter functions.

      SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyKnapsack, consCopyKnapsack) );
      SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveKnapsack) );
      SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveKnapsack) );
      SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteKnapsack) );
      SCIP_CALL( SCIPsetConshdlrDelvars(scip, conshdlr, consDelvarsKnapsack) );
      SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitKnapsack) );

4. If the constraint handler is a specialization of a general linear or nonlinear constraint, we want to include an automatic upgrading mechanism by calling the interface method

      if( SCIPfindConshdlr(scip,"linear") != NULL )
      {
         /* include the linear constraint to knapsack constraint upgrade in the linear constraint handler */
         SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdKnapsack, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );

   or

   SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, nonlinconsUpgdSubtour, NULL, NONLINCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );

   in the nonlinear case. See also cons_nonlinear.h for further information about the general upgrade procedure in the nonlinear case.

5. You may also add user parameters for your constraint handler. Some parameters which are important to play with are added to every constraint automatically, as, e.g., propagation or separation frequency.

      SCIP_CALL( SCIPaddIntParam(scip,
            "constraints/" CONSHDLR_NAME "/sepacardfreq",
            "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
            &conshdlrdata->sepacardfreq, TRUE, DEFAULT_SEPACARDFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
      return SCIP_OKAY;
   }

The methods SCIPcreateConsSubtour() and SCIPcreateConsSubtourBasic() are called to create a single constraint of the constraint handler's constraint class. It should allocate and fill the constraint data, and call SCIPcreateCons(). Take a look at the following example from the knapsack constraint handler:

SCIP_RETCODE SCIPcreateConsKnapsack(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
   const char*           name,               /**< name of constraint */
   int                   nvars,              /**< number of items in the knapsack */
   SCIP_VAR**            vars,               /**< array with item variables */
   SCIP_Longint*         weights,            /**< array with item weights */
   SCIP_Longint          capacity,           /**< capacity of knapsack (right hand side of inequality) */
   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
                                              *   Usually set to TRUE. */
   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
                                              *   Usually set to TRUE. */
   SCIP_Bool             local,              /**< is constraint only valid locally?
                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
                                              *   adds coefficients to this constraint. */
   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
                                              *   Usually set to FALSE. Set to TRUE for own cuts which
                                              *   are separated as constraints. */
   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
                                              *   if it may be moved to a more global node?
                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
   )
{
   SCIP_CONSHDLRDATA* conshdlrdata;
   SCIP_CONSHDLR* conshdlr;
   SCIP_CONSDATA* consdata;

   /* find the knapsack constraint handler */
   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
   if( conshdlr == NULL )
   {
      SCIPerrorMessage("knapsack constraint handler not found\n");
      return SCIP_PLUGINNOTFOUND;
   }

   /* get event handler */
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   assert(conshdlrdata->eventhdlr != NULL);

   /* create constraint data */
   SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, weights, capacity) );

   /* create constraint */
   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
         local, modifiable, dynamic, removable, stickingatnode) );

   /* catch events for variables */
   if( SCIPisTransformed(scip) )
   {
      SCIP_CALL( catchEvents(scip, *cons, consdata, conshdlrdata->eventhdlr) );
   }

   return SCIP_OKAY;
}

In this example, consdataCreate() is a local method that allocates memory for the given consdata and fills the data with the given vars array. For allocating memory for the constraint data, you can use SCIP memory allocation:

SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );

Callback methods of Constraint handlers

Besides the various functions which you will implement inside your constraint handler there exists a number of callback methods associated with your constraint handler. Callback methods can be regarded as tasks which your constraint handler is able to provide to the solver. They are grouped into two categories:

Fundamental Callback methods are mandatory to implement such that your code will work. For example, every constraint handler has to provide the functionality to state whether all of its constraints are fulfilled by a given variable assignment. Hence, the CONSCHECK callback is one of the fundamental (or basic) callbacks of a constraint handler.

Callbacks which are not necessarily implemented are grouped together as additional callbacks. Such callbacks can be used to allocate and free memory at different stages of the solving process. Although not mandatory, it might be useful to implement some of these callbacks, e.g., to extend your constraint handler by a separation or presolving functionality.

All callbacks should be passed to SCIP during the SCIPinclude<PLUGINTYPE><PLUGINNAME> method (e.g., SCIPincludeConshdlrKnapsack() for the knapsack constraint handler). Since SCIP version 3.0, two ways of setting callbacks can be used, either via SCIPincludeConshdlr() (all at once, as it always was), or via SCIPincludeConshdlrBasic() and setter functions for additional callbacks. Since the basic inclusion methods are very unlikely to change and will thus make your code more stable towards future versions of SCIP with more callbacks, we recommend the latter choice, as explained in the interface section.

Fundamental Callback Methods

By implementing the fundamental callbacks, you define the semantics of the constraint class the constraint handler deals with. If these methods are implemented, the resulting code is already correct and finds the optimal solution to the given problem instance. However, it might be very slow because the additional features, like cut separation and domain propagation, are missing. In the C++ wrapper class scip::ObjConshdlr, the fundamental callback methods are virtual abstract member functions. You have to implement them in order to be able to construct an object of your constraint handler class.

There are three fundamental callback methods that are all dealing with the feasibility of a given solution. They are called at different places in the algorithm and have slightly different meaning. However, it is usually reasonable to implement a single local method that is called by all of the three callback methods with slightly modified parameters. The fourth method provides dual information that is used for example in preprocessing.

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

CONSCHECK

The CONSCHECK callback gets a primal solution candidate in a SCIP_SOL* data structure and has to check this solution for global feasibility. It has to return a result SCIP_FEASIBLE, if the solution satisfies all the constraints of the constraint handler, and a result SCIP_INFEASIBLE if there is at least one constraint that is violated.

If the solution is not NULL, SCIP should also be informed about the constraint violation with a call to SCIPupdateSolConsViolation() and additionally SCIPupdateSolLPRowViolation() for every row of the constraint's current representation in the LP relaxation, if any such rows exist. As a convenience method, SCIPupdateSolLPConsViolation() can be used if the constraint is represented completely by a set of LP rows, meaning that the current constraint violation is equal to the maximum of the contraint violations of the corresponding LP rows.

The callback is used by primal heuristics to check a constructed solution for feasibility. That means, the constraint handler has to deal with arbitrary solutions that do not necessarily satisfy the bounds and constraints of the local subproblem.

The value of a variable var in the given solution sol can be accessed by calling

SCIPgetSolVal(scip, sol, var)

For example, the knapsack constraint handler loops over its constraints and calculates the scalar product \(w^T x\) of weights \(w\) with the solution vector \(x\). This scalar product is compared with the capacity of the knapsack constraint. If it exceeds the capacity, the CONSCHECK method is immediately aborted with the result SCIP_INFEASIBLE. If all knapsack constraints are satisfied, a result SCIP_FEASIBLE is returned.

CONSENFOLP

The CONSENFOLP method is called after the price-and-cut loop was finished and an LP solution is available. Like the CHECK call, the ENFOLP method should return a result SCIP_FEASIBLE, if the solution satisfies all the constraints. However, the behavior should be different, if the solution violates some of the associated constraints. The constraint handler may return a result SCIP_INFEASIBLE in this situation, but this is not the best what one can do. The ENFOLP method has the possibility of resolving the infeasibility by

• stating that the current subproblem is infeasible (result SCIP_CUTOFF),
• adding an additional constraint that resolves the infeasibility (result SCIP_CONSADDED),
• reducing the domain of a variable (result SCIP_REDUCEDDOM),
• adding a cutting plane (result SCIP_SEPARATED),
• tightening the LP primal feasibility tolerance and requesting to solve the LP again (result SCIP_SOLVELP),
• performing a branching (result SCIP_BRANCHED).

Note that in case SCIP_CONSADDED, the added constraints must be created with flag initial=TRUE.

However, the solution is not given as a SCIP_SOL* data structure.

The value of a variable var in the LP solution can be accessed by calling

SCIPgetVarSol(scip, var)

or by

SCIPgetSolVal(scip, NULL, var)

By using the latter method, you can have a single local method to check a solution for feasibility by passing the given sol to the CONSCHECK call and by passing a NULL pointer as sol to the CONSENFOLP and CONSENFOPS calls.

CONSENFOPS

The CONSENFOPS callback is similar to the CONSENFOLP callback, but deals with pseudo solutions instead of LP solutions.

If the LP was not solved at the current subproblem (either because the user did not want to solve it, or because numerical difficulties in the LP solving process were detected) no LP solution is available. In this situation, the pseudo solution is used instead. In this solution, the variables are set to the local bound which is best with respect to the objective function. You can think of the pseudo solution as solution to the LP relaxation with all constraints except the bounds being removed.

Like the ENFOLP callback, the ENFOPS callback has to check whether the pseudo solution satisfies all the constraints of the constraint handler. The pseudo solution can be accessed by the same methods as the LP solution (SCIP knows, if the LP was solved at the current subproblem, and returns either the LP solution or the pseudo solution).

Unlike the ENFOLP callback, the ENFOPS callback must not add cuts and cannot return the result SCIP_SEPARATED. It is, however, possible to force the solving of the LP by returning the result SCIP_SOLVELP. For example, the infeasibility of a linear constraint that contains continuous variables cannot be resolved, if all integer variables in the constraint are already fixed. In this case, the LP has to be solved in order to get a solution that satisfies the linear constraint.

CONSENFORELAX

The CONSENFORELAX callback is similar to the CONSENFOLP and CONSENFOPS callbacks, but deals with relaxation solutions.

If the best bound computed by a relaxator that includes the whole LP is strictly better than the bound of the LP itself, the corresponding relaxation solution will get enforced. Therefore the CONSENFORELAX callback will only be called for solutions that satisfy all active LP-constraints.

Like the ENFOLP and ENFOPS callbacks, the ENFORELAX callback has to check whether the solution given in sol satisfies all the constraints of the constraint handler. Since the callback is only called for relaxators including the whole LP, cuts may be added with a result of SCIP_SEPARATED, like in the ENFOLP callback. It is also possible to return SCIP_SOLVELP if the relaxation solution is invalid for some reason and the LP should be solved instead.

Note that the CONSENFORELAX callback is only relevant if relaxators are used. Since the basic distribution of the SCIP Optimization Suite does not contain any relaxators, this callback can be ignored unless any relaxators are added via user-plugins.

CONSLOCK

The CONSLOCK callback provides dual information for a single constraint. It has to tell SCIP, which variables are existing in the given constraint, and in which way modifications of these variables may affect the feasibility of the constraint.

For each variable that is affected by the constraint, the callback should call SCIPaddVarLocks():

• If the constraint may become violated by decreasing the value of a variable, it should call SCIPaddVarLocks(scip, var, nlockspos, nlocksneg), saying that rounding down is potentially rendering the (positive) constraint infeasible and rounding up is potentially rendering the negation of the constraint infeasible.
• If the constraint may become violated by increasing the value of a variable, it should call SCIPaddVarLocks(scip, var, nlocksneg, nlockspos), saying that rounding up is potentially rendering the constraint's negation infeasible and rounding down is potentially rendering the constraint itself infeasible.
• If the constraint may become violated by changing the variable in any direction, it should call SCIPaddVarLocks(scip, var, nlockspos + nlocksneg, nlockspos + nlocksneg).

Note: You do not have to worry about nlockspos and nlocksneg. These integer values are given as parameter of the CONSLOCK callback (see type_cons.h). Just use these variables in the above described fashion without adding or subtracting anything to them. In case of the knapsack constraints this method looks like this.

static
SCIP_DECL_CONSLOCK(consLockKnapsack)
{  /*lint --e{715}*/
   SCIP_CONSDATA* consdata;
   int i;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   for( i = 0; i < consdata->nvars; i++)
   {
      SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlocksneg, nlockspos) );
   }

   return SCIP_OKAY;
}

To give same more intuition, consider the linear constraint \(3x -5y +2z \leq 7\) as an example. The CONSLOCK callback method of the linear constraint handler should call SCIPaddVarLocks(scip, x, nlocksneg, nlockspos), SCIPaddVarLocks(scip, y, nlockspos, nlocksneg), and SCIPaddVarLocks(scip, z, nlocksneg, nlockspos) to tell SCIP, that rounding up of \(x\) and \(z\) and rounding down of \(y\) can destroy the feasibility of the constraint, while rounding down of \(x\) and \(z\) and rounding up of \(y\) can destroy the feasibility of the constraint's negation \(3x -5y +2z > 7\).
A linear constraint \(2 \leq 3x -5y +2z \leq 7\) should call SCIPaddVarLocks(scip, ..., nlockspos + nlocksneg, nlockspos + nlocksneg) on all variables, since rounding in both directions of each variable can destroy both the feasibility of the constraint and it's negation \(3x -5y +2z < 2\) or \(3x -5y +2z > 7\).

Additional Callback Methods

The additional callback methods do not need to be implemented in every case, but provide useful functionality for many applications. They can be added to your constraint handler via setter functions, see here.

CONSFREE

If you are using constraint handler data, you have to implement this method in order to free the constraint handler data. This can be done by the following procedure (which is taken from the knapsack constraint handler):

static
SCIP_DECL_CONSFREE(consFreeKnapsack)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;

   /* free constraint handler data */
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);

   SCIPfreeBlockMemory(scip, &conshdlrdata);

   SCIPconshdlrSetData(conshdlr, NULL);

   return SCIP_OKAY;
}

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

CONSHDLRCOPY

The CONSHDLRCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as NULL the user disables the inclusion of the specified constraint handler into all copied SCIP instances. This may deteriorate the performance of primal heuristics solving sub-SCIPs, since these constitute only relaxations of the original problem if constraint handlers are missing.

A usual implementation just calls the interface method which includes the constraint handler to the model. For example, this callback is implemented for the knapsack constraint handler as follows:

static
SCIP_DECL_CONSHDLRCOPY(conshdlrCopyKnapsack)
{  /*lint --e{715}*/
   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);

   /* call inclusion method of constraint handler */
   SCIP_CALL( SCIPincludeConshdlrKnapsack(scip) );

   *valid = TRUE;

   return SCIP_OKAY;
}

Note: If you implement this callback, take care when setting the valid pointer.

A problem copy is called valid if it is valid in both the primal and the dual sense, i.e., if

• it is a relaxation of the source problem
• it does not enlarge the feasible region.

A constraint handler may choose to not copy a constraint and still declare the resulting copy as valid. It must ensure the feasibility of any solution to the problem copy in the original (source) space.

Note: If you implement this callback and the constraint handler needs constraints (see CONSHDLR_NEEDSCONS), then you also need to implement the callback CONSCOPY.

CONSINIT

The CONSINIT callback is executed after the problem is transformed. The constraint handler may, e.g., use this call to replace the original variables in its constraints by transformed variables, or to initialize its statistical constraint handler data.

CONSEXIT

The CONSEXIT callback is executed before the transformed problem is freed. In this method, the constraint handler should free all resources that were allocated for the solving process.

CONSINITPRE

The CONSINITPRE callback is executed before the preprocessing is started, even if presolving is turned off. The constraint handler may use this call to initialize its presolving data, or to modify its constraints before the presolving process begins. Necessary constraint modifications that have to be performed even if presolving is turned off should be done here or in the presolving deinitialization call.

CONSEXITPRE

The CONSEXITPRE callback is executed after the preprocessing has been finished, even if presolving is turned off. The constraint handler may use this call e.g. to clean up its presolving data, or to finally modify its constraints before the branch-and-bound process begins. Necessary constraint modifications that have to be performed even if presolving is turned off should be done here or in the presolving initialization call. Besides necessary modifications and clean up, no time consuming operations should be done.

CONSINITSOL

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

CONSEXITSOL

The CONSEXITSOL callback is executed before the branch-and-bound process is freed. The constraint handler 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.

CONSDELETE

The CONSDELETE callback is executed if a constraint should be freed. You can think of it as the destructor of a single constraint. In the callback, you have to free the given constraint data. The CONSDELETE callback is therefore the counterpart of the SCIPcreateCons...() interface method and the CONSTRANS method.

CONSTRANS

The CONSTRANS method is called for each constraint of the constraint handler, when the user starts the solving process. It has to copy the original constraint data of the constraint to the memory for the transformed problem. You can think of it as a copy constructor for a single constraint.

The original model is copied in order to protect it from transformations that are applied during the solving process, in particular during preprocessing. Preprocessing and solving always operates on the transformed problem. If the solving process data are freed, the original data still exist and the user can, e.g., modify the problem and restart the solving process.

If you do not implement the CONSTRANS method, a transformed constraint is created with the same flags and the same constraint data pointer. That means, the transformed constraint points to the original constraint data. This is okay, as long as the constraint data is not changed during the solving process. If you want to implement preprocessing methods or other methods that modify the constraint data, you have to implement the CONSTRANS method and create a copy of the constraint data.

Here is an example, which is taken from the knapsack constraint handler:

static
SCIP_DECL_CONSTRANS(consTransKnapsack)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;
   SCIP_CONSDATA* sourcedata;
   SCIP_CONSDATA* targetdata;

   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
   assert(sourcecons != NULL);
   assert(targetcons != NULL);

   sourcedata = SCIPconsGetData(sourcecons);
   assert(sourcedata != NULL);
   assert(sourcedata->row == NULL);  /* in original problem, there cannot be LP rows */

   /* get event handler */
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   assert(conshdlrdata->eventhdlr != NULL);

   /* create target constraint data */
   SCIP_CALL( consdataCreate(scip, &targetdata,
         sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) ); 

   /* create target constraint */
   SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
         SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
         SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
         SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 
         SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );

   /* catch events for variables */
   SCIP_CALL( catchEvents(scip, *targetcons, targetdata, conshdlrdata->eventhdlr) );

   return SCIP_OKAY;
}

CONSINITLP

The CONSINITLP callback is executed before the first LP relaxation is solved. It should add the LP relaxations of all "initial" constraints to the LP. The method should scan the constraints array for constraints that are marked initial via calls to SCIPconsIsInitial() and put the LP relaxation of all initial constraints to the LP with calls to SCIPaddCut().

CONSSEPALP

The CONSSEPALP callback is executed during the price-and-cut loop of the subproblem processing. It should try to generate cutting planes for the constraints of the constraint handler 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, a separation callback searches and produces cuts, that are added with a call to SCIPaddCut(). If the cut should be remembered in the global cut pool, it may also call SCIPaddPoolCut(). If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling SCIPcacheRowExtensions() before these additions and SCIPflushRowExtensions() after. However, the callback may also produce domain reductions or add other constraints.

The CONSSEPALP callback has the following options:

• detecting that the node is infeasible in the variables' 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)

Please see also the Optional Constraint Handler properties section to learn about the properties CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP calling CONSSEPALP.

CONSSEPASOL

The CONSSEPASOL callback is executed during separation loop on arbitrary primal solutions. It should try to generate cutting planes for the constraints of the constraint handler 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.

Usually, a separation callback searches and produces cuts, that are added with a call to SCIPaddCut(). If the cut should be remembered in the global cut pool, it may also call SCIPaddPoolCut(). If the cut is constructed via multiple calls to SCIPaddVarToRow(), then performance can be improved by calling SCIPcacheRowExtensions() before these additions and SCIPflushRowExtensions() after. However, the callback may also produce domain reductions or add other constraints.

The CONSSEPASOL callback has the following options:

• detecting that the node is infeasible in the variables' 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)

Please see also the Optional Constraint Handler properties section to learn about the properties CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, and CONSHDLR_DELAYSEPA, which influence the behaviour of SCIP calling CONSSEPASOL.

CONSPROP

The CONSPROP callback is called during the subproblem processing. It should propagate the constraints, which means that it should infer reductions in the variables' local bounds from the current local bounds. This technique, which is the main workhorse of constraint programming, is called "node preprocessing" in the Integer Programming community.

The CONSPROP callback has the following options:

• detecting that the node is infeasible in the variables' bounds and can be cut off (result SCIP_CUTOFF)
• reducing a variable's domain (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)

Please see also the Optional Constraint Handler properties section to learn about the properties CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, and CONSHDLR_PROP_TIMING, which influence the behaviour of SCIP calling CONSPROP.

CONSRESPROP

If the constraint handler should support conflict analysis, it has to supply a CONSRESPROP method. It also should call SCIPinferVarLbCons() or SCIPinferVarUbCons() in domain propagation instead of SCIPchgVarLb() or SCIPchgVarUb() in order to deduce bound changes on variables. In the SCIPinferVarLbCons() and SCIPinferVarUbCons() calls, the handler provides the constraint that deduced the variable's bound change, and an integer value inferinfo that can be arbitrarily chosen.

The propagation conflict resolving method CONSRESPROP 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 constraint 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.

Note: The fact that inferinfo is an integer, as opposed to an arbitrary data object, is a compromise between space and speed. Sometimes a propagator would need more information to efficiently infer the original propagation steps that lead to the conflict. This would, however, require too much space. In the extreme, the original propagation steps have to be repeated.

For example, the logicor constraint \(c = x \vee y \vee z\) fixes variable \(z\) to TRUE (i.e., changes the lower bound of \(z\) to 1.0), if both, \(x\) and \(y\), are assigned to FALSE (i.e., if the upper bounds of these variables are 0.0). It uses SCIPinferVarLbCons(scip, z, 1.0, c, 0) to apply this assignment (an inference information tag is not needed by the constraint handler and is set to 0). In the conflict analysis, the constraint handler may be asked to resolve the lower bound change on \(z\) with constraint \(c\), that was applied at a time given by a bound change index "bdchgidx". With a call to SCIPvarGetLbAtIndex(z, bdchgidx), the handler can find out, that the lower bound of variable \(z\) was set to 1.0 at the given point of time, and should call SCIPaddConflictUb(scip, x, bdchgidx) and SCIPaddConflictUb(scip, y, bdchgidx) to tell SCIP, that the upper bounds of \(x\) and \(y\) at this point of time were the reason for the deduction of the lower bound of \(z\).

If conflict analysis should not be supported, the method has to set the result code to SCIP_DIDNOTFIND. Although this is a viable approach to circumvent the implementation of the usually rather complex conflict resolving method, 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.

CONSPRESOL

The CONSPRESOL callback is called during preprocessing. It should try to tighten the domains of the variables, tighten the coefficients of the constraints of the constraint handler, delete redundant constraints, aggregate and fix variables if possible, and upgrade constraints to more specific types.

If the CONSPRESOL callback applies changes to the constraint data, you also have to implement the CONSTRANS callback in order to copy the constraint data to the transformed problem space and protect the original problem from the preprocessing changes.

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 constraint is infeasible in the variable's bounds
• SCIP_SUCCESS : the presolver found a 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 Constraint Handler properties section to learn about the properties CONSHDLR_PRESOLTIMING and CONSHDLR_MAXPREROUNDS, which influence the behaviour of SCIP calling CONSPRESOL.

CONSACTIVE

The CONSACTIVE callback method is called each time a constraint of the constraint handler is activated. For example, if a constraint is added locally to a subproblem, the CONSACTIVE callback is called whenever the search enters the subtree where the constraint exists.

CONSDEACTIVE

The CONSDEACTIVE callback method is called each time a constraint of the constraint handler is deactivated. For example, if a constraint is added locally to a subproblem, the CONSDEACTIVE callback is called whenever the search leaves the subtree where the constraint exists.

CONSENABLE

The CONSENABLE callback method is called each time a constraint of the constraint handler is enabled. Constraints might be active without being enabled. In this case, only the feasibility checks are executed, but domain propagation and separation is skipped.

CONSDISABLE

The CONSDISABLE callback method is called each time a constraint of the constraint handler is disabled.

CONSPRINT

The CONSPRINT callback method is called, when the user asks SCIP to display the problem to the screen or save the problem into a file. This is, however, only the case if the user requested the CIP format. For more details about reading and writing with SCIP we refer to the file readers. In this callback method the constraint handler should display the data of the constraint in an appropriate form. The output format that is defined by the CONSPRINT callbacks is called CIP format. In later versions of SCIP, the constraint handlers should also be able to parse (i.e., read) constraints which are given in CIP format.

CONSCOPY

The CONSCOPY callback method is used whenever constraints should be copied from one SCIP instance into another SCIP instance. This method comes with the necessary parameters to do so, most importantly with a mapping of the variables of the source SCIP instance to the corresponding variables of the target SCIP instance, and a mapping for the constraints in the same way. For a complete list of all arguments of this callback method see type_cons.h.

To get the corresponding target variable of a given source variable, you can use the variable map directly:

targetvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, sourcevar);

We recommend, however, to use the method SCIPgetVarCopy() which gets besides others the variable map and the constraint map as input and returns the requested target variable. The advantage of using SCIPgetVarCopy() is that in the case the required variable does not yet exist, it is created and added to the copy automatically:

SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevar, &targetvar, varmap, consmap, global) );

Finally, the result pointer valid has to be set to TRUE if (and only if!) the copy process was successful.

Note: Be careful when setting the valid pointer. A problem copy is called valid if it is valid in both the primal and the dual sense, i.e., if

• it is a relaxation of the source problem
• it does not enlarge the feasible region.

A constraint handler may choose to not copy a constraint and still declare the resulting copy as valid. Therefore, it must ensure the feasibility of any solution to the problem copy in the original (source) space.

For an example implementation we refer to cons_linear.h. Additional documentation and the complete list of all parameters can be found in the file in type_cons.h.

CONSPARSE

This method is the counter part to CONSPRINT. The ideal idea is that a constraint handler is able to parse the output which it generated via the CONSPRINT method and creates the corresponding constraint. If the parsing was successfully the result pointer success should be set to TRUE. An example implementation can be found in the linear constraint handler.

CONSDELVARS

This method should iterate over the given constraints and delete all variables that were marked for deletion by SCIPdelVar(). Variable deletion is especially interesting for branch-cut-and-price applications. If your constraint handler allows the addition of variables during the solving process (see "modifiable" attribute of constraints), then you might also want to implement this callback. This would allow you to not only create variables during solving, but also remove them dynamically from the problem to reduce memory consumption in case they are no longer necessary. During presolving, SCIP may also find that some variables are not needed anymore and then try to delete them. Thus, if you do not implement this callback, the constraint handler should capture its variables via SCIPcaptureVar() to prevent SCIP from erroneously deleting them.

Additional documentation and the complete list of all parameters can be found in the file type_cons.h.

CONSGETVARS

The CONSGETVARS callback of a constraint handler can be implemented to give access to the constraint variables as array, independently from the internal data structure of the constraint. The buffer array is already passed, together with its length. Consider implementing CONSGETNVARS, too, to have information about the number of variables in this constraint.

CONSGETNVARS

This callback can be implemented to return the number of variables involved into a particular constraint. In order to have access to the variable pointers, consider implementing CONSGETVARS.

/** constraint method of constraint handler which returns the number of variables (if possible) */
static
SCIP_DECL_CONSGETNVARS(consGetNVarsLinear)
{  /*lint --e{715}*/
   SCIP_CONSDATA* consdata;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   (*nvars) = consdata->nvars;
   (*success) = TRUE;

   return SCIP_OKAY;
}

CONSGETDIVEBDCHGS

This callback is used inside the various diving heuristics of SCIP and does not affect the normal branching of the actual search. The constraint handler can provide this callback to render a current working solution (even more) infeasible by suggesting one or several variable bound changes.

Further documentation

Further documentation can be found in type_cons.h for callback descriptions and a complete list of all callback parameters, or in scip.h for globally available functions.