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 TSP example 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"):
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:
The following properties are optional and only need to be defined if the constraint handlers support separation, presolving, propagation, and/or upgrade functionality.
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.
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:
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.
Now, SCIP gets notified of the presence of the constraint handler together with its basic callbacks.
All additional callbacks are added via their setter functions.
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
in the nonlinear case. See also cons_nonlinear.h for further information about the general upgrade procedure in the nonlinear case.
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:
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:
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.
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.
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. 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
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.
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
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
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.
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.
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():
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.
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\).
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.
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):
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.
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:
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
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.
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.
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.
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.
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.
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.
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.
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.
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:
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().
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(). However, the callback may also produce domain reductions or add other constraints.
The CONSSEPALP callback has the following options:
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.
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(). However, the callback may also produce domain reductions or add other constraints.
The CONSSEPASOL callback has the following options:
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.
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.
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:
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.
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.
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:
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.
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.
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.
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.
The CONSDISABLE callback method is called each time a constraint of the constraint handler is disabled.
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.
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:
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:
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
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.
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.
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.
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.
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.
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.