How to add relaxation handlers SCIP provides specific support for LP relaxations of constraint integer programs. In addition, relaxation handlers, also called relaxators, can be used to include other relaxations, e.g. Lagrange relaxations or semidefinite relaxations. The relaxation handler manages the necessary data structures and calls the relaxation solver to generate dual bounds and primal solution candidates. Additional documentation for the callback methods of a relaxation handler can be found in the file type_relax.h. Here is what you have to do to implement a relaxation handler:
Properties of a Relaxation HandlerAt the top of the new file "relax_myrelaxator.c" you can find the relaxation handler properties. These are given as compiler defines. In the C++ wrapper class, you have to provide the relaxation handler properties by calling the constructor of the abstract base class scip::ObjRelax from within your constructor. The properties you have to set have the following meaning:
Relaxation Handler DataBelow the header "Data structures" you can find a struct which is called "struct SCIP_RelaxData". In this data structure, you can store the data of your relaxation handler. For example, you should store the adjustable parameters of the relaxation handler in this data structure. If you are using C++, you can add relaxation handler data as usual as object variables to your class. Interface MethodsAt the bottom of "relax_myrelaxator.c", you can find the interface method SCIPincludeRelaxMyrelaxator(), which also appears in "relax_myrelaxator.h". SCIPincludeRelaxMyrelaxator() is called by the user, if (s)he wants to include the relaxation handler, i.e., if (s)he wants to use the relaxation handler in his/her application. This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the relaxation handler. For this, you can either call SCIPincludeRelax(), or SCIPincludeRelaxBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetRelaxCopy(). We recommend this latter variant because it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first variant must be manually adjusted with every SCIP release containing new callbacks for relaxation handlers in order to compile. If you are using relaxation handler data, you have to allocate the memory for the data at this point. You can do this by calling: SCIP_CALL( SCIPallocMemory(scip, &relaxdata) ); You also have to initialize the fields in struct SCIP_RelaxData afterwards. You may also add user parameters for your relaxation handler, see the method SCIPincludeConshdlrKnapsack() in the knapsack constraint handler for an example of how to add user parameters. Fundamental Callback Methods of a Relaxation HandlerThe fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. They are passed together with the relaxation handler itself to SCIP using SCIPincludeRelax() or SCIPincludeRelaxBasic(), see Interface Methods. Relaxation handler plugins have only one fundamental callback method, namely the RELAXEXEC method. This method has to be implemented for every relaxation handler; the other callback methods are optional. In the C++ wrapper class scip::ObjRelax, the scip_exec() method (which corresponds to the RELAXEXEC callback) is a virtual abstract member function. You have to implement it in order to be able to construct an object of your relaxation handler class. Additional documentation for the callback methods can be found in type_relax.h. RELAXEXECThe RELAXEXEC is called in each relaxation solving round. It should solve the current subproblem's relaxation. Note that, like the LP relaxation, the relaxation handler should only operate on variables for which the corresponding column exists in the transformed problem. Typical methods called by a relaxation handler are SCIPconstructLP() and SCIPflushLP() to make sure that the LP of the current node is constructed and its data can be accessed via calls to SCIPgetLPRowsData() and SCIPgetLPColsData(), SCIPseparateSol() to call the cutting plane separators for a given primal solution, and SCIPupdateLocalLowerbound() to update the current node's dual bound after having solved the relaxation. In addition, you may want to call SCIPtrySolFree() if you think that you have found a feasible primal solution. The primal solution of the relaxation can be stored inside the data structures of SCIP with Usually, the RELAXEXEC callback only solves the relaxation and provides a lower (dual) bound with a call to SCIPupdateLocalLowerbound(). However, it may also produce domain reductions, add additional constraints or generate cutting planes. It has the following options:
In the above criteria, "the same relaxation" means that the LP relaxation stayed unmodified. This means in particular that no row has been added and no bounds have been modified. For example, changing the bounds of a variable will, as long as it was a COLUMN variable, lead to a modification in the LP such that the relaxation handler is called again after it returned with the result code SCIP_REDUCEDDOM. Additional Callback Methods of a Relaxation HandlerThe additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications, they can be used, for example, to initialize and free private data. Additional callbacks can either be passed directly with SCIPincludeRelax() to SCIP or via specific setter functions after a call of SCIPincludeRelaxBasic(), see also Interface Methods. RELAXFREEIf you are using relaxation handler data, you have to implement this method in order to free the relaxation handler data. This can be done by the following procedure: static SCIP_DECL_RELAXFREE(relaxFreeMyrelaxator) { SCIP_RELAXDATA* relaxdata; relaxdata = SCIPrelaxGetData(relax); assert(relaxdata != NULL); SCIPfreeMemory(scip, &relaxdata); SCIPrelaxSetData(relax, NULL); return SCIP_OKAY; } If you have allocated memory for fields in your relaxation handler data, remember to free this memory before freeing the relaxation 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. RELAXINITThe RELAXINIT callback is executed after the problem is transformed. The relaxation handler may, e.g., use this call to initialize its relaxation handler data. RELAXCOPYThe RELAXCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as RELAXEXITThe RELAXEXIT callback is executed before the transformed problem is freed. In this method, the relaxation handler should free all resources that have been allocated for the solving process in RELAXINIT. RELAXINITSOLThe RELAXINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin. The relaxation handler may use this call to initialize its branch-and-bound specific data. REALXEXITSOLThe RELAXEXITSOL callback is executed before the branch-and-bound process is freed. The relaxation handler should use this call to clean up its branch-and-bound data. |