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. 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"):
Properties of a Constraint HandlerAt 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
Optional Constraint Handler propertiesThe following properties are optional and only need to be defined if the constraint handlers support separation, presolving, propagation, and/or upgrade functionality.
Constraint Data and Constraint Handler DataBelow 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. Interface MethodsAt 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 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* scip, SCIP_CONS** cons, const char* name, int nvars, SCIP_VAR** vars, SCIP_Longint* weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode ) { SCIP_CONSHDLRDATA* conshdlrdata; SCIP_CONSHDLR* conshdlr; SCIP_CONSDATA* consdata; conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); if( conshdlr == NULL ) { SCIPerrorMessage("knapsack constraint handler not found\n"); return SCIP_PLUGINNOTFOUND; } conshdlrdata = SCIPconshdlrGetData(conshdlr); assert(conshdlrdata != NULL); assert(conshdlrdata->eventhdlr != NULL); SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, weights, capacity) ); SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 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 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); Callback methods of Constraint handlersBesides 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 MethodsBy 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. CONSCHECKThe 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 SCIPgetSolVal(scip, sol, var) For example, the knapsack constraint handler loops over its constraints and calculates the scalar product of weights with the solution vector . 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. CONSENFOLPThe 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 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 CONSENFOPSThe 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. CONSLOCKThe 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. static SCIP_DECL_CONSLOCK(consLockKnapsack) { SCIP_CONSDATA* consdata; int i; consdata = SCIPconsGetData(cons); assert(consdata != NULL); for( i = 0; i < consdata->nvars; i++) { SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlocksneg, nlockspos) ); } return SCIP_OKAY; } To give same more intuition, consider the linear constraint 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 and and rounding down of can destroy the feasibility of the constraint, while rounding down of and and rounding up of can destroy the feasibility of the constraint's negation . Additional Callback MethodsThe 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. CONSFREEIf 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) { SCIP_CONSHDLRDATA* conshdlrdata; conshdlrdata = SCIPconshdlrGetData(conshdlr); assert(conshdlrdata != NULL); SCIPfreeMemory(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. CONSHDLRCOPYThe CONSHDLRCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as 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) { assert(scip != NULL); assert(conshdlr != NULL); assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); SCIP_CALL( SCIPincludeConshdlrKnapsack(scip) ); *valid = TRUE; return SCIP_OKAY; } Note: If you implement this callback, take care when setting the valid pointer. The valid pointer should be set to TRUE if (and only if!) you can make sure that all necessary data of the constraint handler are copied correctly. If the complete problem is validly copied, i.e. if the copy methods of all problem defining plugins (constraint handlers and pricers) return Note: If you implement this callback and the constraint handler needs constraints (see CONSHDLR_NEEDSCONS), then you also need to implement the callback CONSCOPY. CONSINITThe 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. CONSEXITThe 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. CONSINITPREThe 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. CONSEXITPREThe 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. CONSINITSOLThe 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. CONSEXITSOLThe 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. CONSDELETEThe 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. CONSTRANSThe 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) { 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); conshdlrdata = SCIPconshdlrGetData(conshdlr); assert(conshdlrdata != NULL); assert(conshdlrdata->eventhdlr != NULL); SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr, sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) ); SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); return SCIP_OKAY; } CONSINITLPThe 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(). CONSSEPALPThe 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. CONSSEPASOLThe 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. CONSPROPThe 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. CONSRESPROPIf 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 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 Note: The fact that For example, the logicor constraint fixes variable to TRUE (i.e., changes the lower bound of to 1.0), if both, and , are assigned to FALSE (i.e., if the upper bounds of these variables are 0.0). It uses 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. CONSPRESOLThe 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. CONSACTIVEThe 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. CONSDEACTIVEThe 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. CONSENABLEThe 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. CONSDISABLEThe CONSDISABLE callback method is called each time a constraint of the constraint handler is disabled. CONSPRINTThe 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. CONSCOPYThe 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: SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevar, &targetvar, varmap, consmap, global) ); Finally, the result pointer Note: Be careful when setting the valid pointer. If you set the valid pointer to TRUE, but the constraint was not copied one-to-one, then optimal solutions might be cut off during the search (see section CONSHDLRCOPY above). 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. CONSPARSEThis 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. CONSDELVARSThis 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. CONSGETVARSThe 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. CONSGETNVARSThis 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. CONSGETDIVEBDCHGSThis 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 documentationFurther 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. |