Scippy

SCIP

Solving Constraint Integer Programs

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.
However, the data to define a single relaxation must either be extracted by the relaxation handler itself (e.g., from the user defined problem data, the LP information, or the integrality conditions), or be provided by the constraint handlers. In the latter case, the constraint handlers have to be extended to support this specific relaxation.
We now explain how users can add their own relaxation handlers using the C interface. As an example, look into the NLP relaxation handler of the Relaxator example (examples/Relaxator/src/relax_nlp.c). It is very easy to transfer the C explanation to C++: whenever a method should be implemented using the SCIP_DECL_RELAX... notion, reimplement the corresponding virtual member function of the abstract scip::ObjRelax wrapper base class.

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:

  1. Copy the template files src/scip/relax_xyz.c and src/scip/relax_xyz.h into files named "relax_myrelaxator.c" and "relax_myrelaxator.h".
    Make sure to adjust your Makefile such that these files are compiled and linked to your project.
  2. Use SCIPincludeRelaxMyrelaxator() in order to include the relaxation handler into your SCIP instance, e.g, in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
  3. Open the new files with a text editor and replace all occurrences of "xyz" by "myrelaxator".
  4. Adjust the properties of the relaxation handler (see Properties of a Relaxation Handler).
  5. Define the relaxation handler data (see Relaxation Handler Data). This is optional.
  6. Implement the interface methods (see Interface Methods).
  7. Implement the fundamental callback methods (see Fundamental Callback Methods of a Relaxation Handler).
  8. Implement the additional callback methods (see Additional Callback Methods of a Relaxation Handler). This is optional.

Properties of a Relaxation Handler

At 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:

RELAX_NAME: the name of the relaxation handler.
This name is used in the interactive shell to address the relaxation handler. Additionally, if you are searching for a relaxation handler with SCIPfindRelax(), this name is looked up. Names have to be unique: no two relaxation handlers may have the same name.
RELAX_DESC: the description of the relaxation handler.
This string is printed as a description of the relaxation handler in the interactive shell.
RELAX_PRIORITY: the priority of the relaxation handler.
During each relaxation solving round, the included relaxation handlers and the price-and-cut loop for solving the LP relaxation are called in a predefined order, which is given by the priorities of the relaxation handlers. First, the relaxation handlers with non-negative priority are called in the order of decreasing priority. Next, the price-and-cut loop for solving the LP relaxation is executed. Finally, the relaxation handlers with negative priority are called in the order of decreasing priority.
Usually, you will have only one relaxation handler in your application and thus only have to decide whether it should be called before or after solving the LP relaxation. For this decision you should consider the complexity of the relaxation solving algorithm and the impact of the resulting solution: if your relaxation handler provides a fast algorithm that usually has a high impact (i.e. the relaxation is a good approximation of the feasible region of the subproblem and the solution severely improves the dual bound), it should have a non-negative priority.
Note that for certain applications, it is useful to disable the LP relaxation and only use your custom relaxation. This can easily be achieved by setting the "lp/solvefreq" parameter to -1.
RELAX_FREQ: the default frequency for solving the relaxation.
The frequency defines the depth levels at which the relaxation solving method RELAXEXEC is called. For example, a frequency of 7 means, that the relaxation solving callback is executed for subproblems that are in depth 0, 7, 14, ... of the branching tree. A frequency of 0 means that the callback is only executed at the root node, i.e., only the relaxation of the root problem is solved. A frequency of -1 disables the relaxation handler.
RELAX_INCLUDESLP: whether the whole lp is included in the relaxation.
This flag should be set to TRUE if all active LP-rows are included in the relaxation and every feasible solution produced by the relaxator will satisfy all these LP-constraints. Only if this is set to TRUE, the solutions of this relaxator can be enforced using the CONSENFORELAX callback, meaning that they will be used as primal solutions if feasible and can be separated or branched on. If this flag is set to FALSE, only the lowerbound computed by the relaxator will be used in the solving process.

Relaxation Handler Data

Below 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.
Defining relaxation handler data is optional. You can leave the struct empty.

Interface Methods

At 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( SCIPallocBlockMemory(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 Handler

The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. They are passed together with the 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.

RELAXEXEC

The 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(), and SCIPseparateSol() to call the cutting plane separators for a given primal solution.

The lowerbound computed by the relaxation should be returned in the lowerbound pointer. The primal solution of the relaxation can be stored inside the data structures of SCIP with SCIPsetRelaxSolVal() and SCIPsetRelaxSolVals(). If the RELAX_INCLUDESLP flag is set to true, this solution will be enforced and, if feasible, added to the solution storage if the lowerbound of this relaxator is the largest among all relaxators and the LP. You may also call SCIPtrySolFree() directly from the relaxation handler to make sure that a solution is added to the solution storage if it is feasible, even if the relaxator does not include the LP or another relaxator produced a stronger bound. After the relaxation round is finished, the best relaxation solution can be accessed via SCIPgetRelaxSolVal(). Furthermore, there is a list of external branching candidates, that can be filled by relaxation handlers and constraint handlers, allowing branching rules to take these candidates as a guide on how to split the problem into subproblems. If the relaxation solution is enforced, the integrality constraint handler will add external branching candidates for the relaxation solution automatically, but the relaxation handler can also directly call SCIPaddExternBranchCand().

Usually, the RELAXEXEC callback only solves the relaxation and provides a lower (dual) bound through the corresponding pointer and possibly a solution through SCIPsetRelaxSolVal() calls. However, it may also produce domain reductions, add additional constraints or generate cutting planes. It has the following options:

  • detecting that the node is infeasible in the variable's bounds and can be cut off (result SCIP_CUTOFF)
  • adding an additional constraint and stating that the relaxation handler should not be called again on the same relaxation (result SCIP_CONSADDED)
  • reducing a variable's domain and stating that the relaxation handler should not be called again on the same relaxation (result SCIP_REDUCEDDOM)
  • adding a cutting plane to the LP and stating that the relaxation handler should not be called again on the same relaxation (result SCIP_SEPARATED)
  • stating that the relaxation handler solved the relaxation and should not be called again on the same relaxation (result SCIP_SUCCESS)
  • interrupting the solving process to wait for additional input, e.g., cutting planes (result SCIP_SUSPENDED)
  • stating that the separator was skipped (result SCIP_DIDNOTRUN).

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. If the relaxation solution should be enforced, the relaxation handler has to produce a new solution in this case which satisfies the updated LP. If a relaxation handler should only run once per node to compute a lower bound, it should store the node of the last relaxation call itself and return SCIP_DIDNOTRUN for subsequent calls in the same node.

Additional Callback Methods of a Relaxation Handler

The additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications, they can be used, for example, to initialize and free private data. Additional callbacks can either be passed directly with SCIPincludeRelax() to SCIP or via specific setter functions after a call of SCIPincludeRelaxBasic(), see also Interface Methods.

RELAXFREE

If 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(relaxFreeUnittest)
{ /*lint --e{715}*/
/* call destructor of relaxation handler */
SCIP_RELAXDATA* relaxdata;
relaxdata = SCIPrelaxGetData(relax);
assert(relaxdata != NULL);
SCIPfreeMemory(scip, &relaxdata);
SCIPrelaxSetData(relax, NULL);
return SCIP_OKAY;
}

(Source: unittests/src/unittest-relax/relax_unittest.c)

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.

RELAXINIT

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

RELAXCOPY

The RELAXCOPY callback is executed when a SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as NULL the user disables the execution of the specified relaxation handler for all copied SCIP instances. This may deteriorate the performance of primal heuristics using sub-SCIPs.

RELAXEXIT

The 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.

RELAXINITSOL

The 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.

REALXEXITSOL

The 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.