Scippy

SCIP

Solving Constraint Integer Programs

How to add branching rules

Branching rules are used to split the problem at the current node into smaller subproblems. Branching rules can be called at three different occasions, which is why they have three different execution methods (see Additional Callback Methods of a Branching Rule). Branching is performed if:

  • the LP solution of the current problem is fractional. In this case, the integrality constraint handler calls the BRANCHEXECLP methods of the branching rules.
  • the list of external branching candidates is not empty. This will only be the case if branching candidates were added by a user's relaxation handler or constraint handler plugin, calling SCIPaddExternBranchCand(). These branching candidates should be processed by the BRANCHEXECEXT method.
  • if an integral solution violates one or more constraints and this infeasibility could not be resolved in the callback methods CONSENFOLP and CONSENFOPS of the corresponding constraint handlers. In this case, the BRANCHEXECPS method will be called. This is the standard case, if you use SCIP as a pure CP or SAT solver. If the LP or any other type of relaxation is used, then branching on pseudo solutions works as a last resort.

The idea of branching rules is to take a global view on the problem. In contrast, branching paradigms which are specific to one type of constraint are best implemented within the enforcement callbacks of your constraint handler. See, e.g., the constraint specific branching rules provided by the constraint handlers for special ordered sets (src/scip/cons_sos{1,2}.c)).
All branching rules that come with the default distribution of SCIP create two subproblems by splitting a single variable's domain. It is, however, fully supported to implement much more general branching schemes, for example by creating more than two subproblems, or by adding additional constraints to the subproblems instead of tightening the domains of the variables.
A complete list of all branching rules contained in this release can be found here.

We now explain how users can add their own branching rules. Take the most infeasible LP branching rule (src/scip/branch_mostinf.c) as an example. As all other default plugins, it is written in C. C++ users can easily adapt the code by using the scip::ObjBranchrule wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_BRANCH... callback methods.

Additional documentation for the callback methods of a branching rule can be found in the file type_branch.h.

Here is what you have to do to implement a branching rule:

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

Properties of a Branching Rule

At the top of the new file "branch_mybranchingrule.c" you can find the branching rule properties. These are given as compiler defines. In the C++ wrapper class, you have to provide the branching rule properties by calling the constructor of the abstract base class scip::ObjBranchrule from within your constructor. The properties you have to set have the following meaning:

BRANCHRULE_NAME: the name of the branching rule.
This name is used in the interactive shell to address the branching rule. Additionally, if you are searching for a branching rule with SCIPfindBranchrule(), this name is looked up. Names have to be unique: no two branching rules may have the same name.
BRANCHRULE_DESC: the description of the branching rule.
This string is printed as a description of the branching rule in the interactive shell.
BRANCHRULE_PRIORITY: the default value for the priority of the branching rule.
In the subproblem processing, the branching rules are called in decreasing order of their priority until one succeeded to branch. Since most branching rules are able to generate a branching in all situations, only the rule of highest priority is used. In combination with the BRANCHRULE_MAXDEPTH and BRANCHRULE_MAXBOUNDDIST settings, however, interesting strategies can be easily employed. For example, the user can set the priority of the "full strong branching" strategy to the highest value and assign the second highest value to the "reliable pseudo cost" rule. If (s)he also sets the maximal depth for the "full strong branching" to 5, in the top 5 depth levels of the search tree the "full strong branching" is applied, while in the deeper levels "reliable pseudo cost branching" is used.
Note that the BRANCHRULE_PRIORITY property only specifies the default value of the priority. The user can change this value arbitrarily.
BRANCHRULE_MAXDEPTH: the default value for the maximal depth level of the branching rule.
This parameter denotes the maximal depth level in the branch-and-bound tree up to which the branching method of the branching rule will be applied. Use -1 for no limit.
Note that this property only specifies the default value. The user can change this value arbitrarily.
BRANCHRULE_MAXBOUNDDIST: the default value for the maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching.
At the current branch-and-bound node, the relative distance from its dual bound (local dual bound) to the primal bound compared to the best node's dual bound (global dual bound) is considered. The branching method of the branching rule will only be applied at the node if this relative distance does not exceed BRANCHRULE_MAXBOUNDDIST.
For example, if the global dual bound is 50 and the primal bound is 60, BRANCHRULE_MAXBOUNDDIST = 0.25 means that branching is only applied if the current node's dual bound is in the first quarter of the interval [50,60], i.e., if it is less than or equal to 52.5. In particular, the values 0.0 and 1.0 mean that the branching rule is applied at the current best node only or at all nodes, respectively.
Note that the BRANCHRULE_MAXBOUNDDIST property only specifies the default value of the maximal bound distance. The user can change this value arbitrarily.

Branching Rule Data

Below the header "Data structures" you can find a struct which is called "struct SCIP_BranchruleData". In this data structure, you can store the data of your branching rule. For example, you should store the adjustable parameters of the branching rule in this data structure. If you are using C++, you can add branching rule data as usual as object variables to your class.
Defining branching rule data is optional. You can leave the struct empty.

Interface Methods

At the bottom of "branch_mybranchingrule.c", you can find the interface method SCIPincludeBranchruleMybranchingrule(), which also appears in "branch_mybranchingrule.h" SCIPincludeBranchruleMybranchingrule() is called by the user, if (s)he wants to include the branching rule, i.e., if (s)he wants to use the branching rule in his/her application.

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the branching rule. For this, you can either call SCIPincludeBranchrule(), or SCIPincludeBranchruleBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetBranchruleCopy(). 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 branchrule in order to compile.

If you are using branching rule data, you have to allocate the memory for the data at this point. You can do this by calling:

SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );

You also have to initialize the fields in struct SCIP_BranchruleData afterwards.

You may also add user parameters for your branching rule, see the method SCIPincludeBranchruleRelpscost() in src/scip/branch_relpscost.c for an example.

Fundamental Callback Methods of a Branching Rule

Branching rules do not have any fundamental callback methods, i.e., all callback methods are optional. In most cases, however, you want to implement the BRANCHEXECLP method and sometimes the BRANCHEXECPS method.

Additional Callback Methods of a Branching Rule

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 SCIPincludeBranchrule() to SCIP or via specific setter functions after a call of SCIPincludeBranchruleBasic(), see also Interface Methods.

The most important callback methods are the BRANCHEXECLP, BRANCHEXECEXT, and BRANCHEXECPS methods, which perform the actual task of generating a branching.

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

BRANCHEXECLP

The BRANCHEXECLP callback is executed during node processing if a fractional LP solution is available. It should split the current problem into smaller subproblems. Usually, the branching is done in a way such that the current fractional LP solution is no longer feasible in the relaxation of the subproblems. It is, however, possible to create a child node for which the fractional LP solution is still feasible in the relaxation, for example, by branching on a variable with integral LP value. In every case, you have to make sure that each subproblem is a proper restriction of the current problem. Otherwise, you risk to produce an infinite path in the search tree.

The user gains access to the branching candidates, i.e., to the fractional variables, and their LP solution values by calling the method SCIPgetLPBranchCands(). Furthermore, SCIP provides two methods for performing the actual branching, namely SCIPbranchVar() and SCIPcreateChild().

Given an integral variable $x$ with fractional LP solution value $x^*$, the method SCIPbranchVar() creates two child nodes; one contains the bound $x \le \lfloor x^* \rfloor$ and the other one contains the bound $x \ge \lceil x^* \rceil$, see the BRANCHEXECLP callback in src/scip/branch_mostinf.c for an example. In addition, if a proven lower objective bound of a created child node is known, like after strong branching has been applied, the user may call the method SCIPupdateNodeLowerbound() in order to update the child node's lower bound.

Please also see the further information for the three execution methods.

BRANCHEXECEXT

The BRANCHEXECEXT callback is executed during node processing if no LP solution is available and the list of external branching candidates is not empty. It should split the current problem into smaller subproblems. If you do not use relaxation handlers or constraints handlers that provide external branching candidates, you do not need to implement this callback.

In contrast to the LP branching candidates and the pseudo branching candidates, the list of external branching candidates will not be generated automatically. The user has to add all variables to the list by calling SCIPaddExternBranchCand() for each of them. Usually, this will happen in the execution method of a relaxation handler or in the enforcement methods of a constraint handler.

The user gains access to these branching candidates by calling the method SCIPgetExternBranchCands(). Furthermore, SCIP provides two methods for performing the actual branching with a given solution value, namely SCIPbranchVarVal() and SCIPcreateChild(). SCIPbranchVarVal() allows users to specify the branching point for a variable in contrast to SCIPbranchVar(), which will always use the current LP or pseudo solution.

This paragraph contains additional information regarding how the method SCIPbranchVarVal() works. For external branching candidates, there are three principle possibilities:

  • Given a continuous variable $x$ with solution value $x^*$, the method SCIPbranchVarVal() creates two child nodes; one contains the bound $x \le x^* $ and the other one contains the bound $x \ge x^* $.
  • Given an integer variable $x$ with fractional solution value $x^*$, the method SCIPbranchVarVal() creates two child nodes; one contains the bound $x \le \lfloor x^* \rfloor$ and the other one contains the bound $x \ge \lceil x^* \rceil$.
  • Given an integer variable $x$ with integral solution value $x^*$, the method SCIPbranchVarVal() creates three child nodes; one contains the bound $x \le x^* -1$, one contains the bound $x \ge x^* +1$, one contains the fixing $x = x^*$.

See the BRANCHEXECEXT callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a created child node is known the user may call the method SCIPupdateNodeLowerbound() in order to update the child node's lower bound.

Please also see the further information for the three execution methods.

BRANCHEXECPS

The BRANCHEXECPS callback is executed during node processing if no LP solution is available and at least one of the integer variables is not yet fixed. It should split the current problem into smaller subproblems. PS stands for pseudo solution which is the vector of all variables set to their locally best (w.r.t. the objective function) bounds.

The user gains access to the branching candidates, i.e., to the non-fixed integer variables, by calling the method SCIPgetPseudoBranchCands(). Furthermore, SCIP provides two methods for performing the actual branching, namely SCIPbranchVar() and SCIPcreateChild().

Given an integer variable $x$ with bounds $[l,u]$ and not having solved the LP, the method SCIPbranchVar() creates two child nodes:

  • If both bounds are finite, then the two children will contain the domain reductions $x \le x^*$, and $x \ge x^*+1$ with $x^* = \lfloor \frac{l + u}{2}\rfloor$. The current pseudo solution will remain feasible in one of the branches, but the hope is that halving the domain's size leads to good propagations.
  • If only one of the bounds is finite, the variable will be fixed to that bound in one of the child nodes. In the other child node, the bound will be shifted by one.
  • If both bounds are infinite, three children will be created: $x \le 1$, $x \ge 1$, and $x = 0$.

See the BRANCHEXECPS callback in src/scip/branch_random.c for an example. In addition, if a proven lower bound of a created child node is known, the user may call the method SCIPupdateNodeLowerbound() in order to update the child node's lower bound.

Please also see the further information for the three execution methods.

Further information for the three execution methods

In order to apply more general branching schemes, one should use the method SCIPcreateChild(). After having created a child node, the additional restrictions of the child node have to be added with calls to SCIPaddConsNode(), SCIPchgVarLbNode(), or SCIPchgVarUbNode().
In the method SCIPcreateChild(), the branching rule has to assign two values to the new nodes: a node selection priority for each node and an estimate for the objective value of the best feasible solution contained in the subtree after applying the branching. If the method SCIPbranchVar() is used, these values are automatically assigned. For variable based branching schemes, one might use the methods SCIPcalcNodeselPriority() and the method SCIPcalcChildEstimate().

In some cases, the branching rule can tighten the current subproblem instead of producing a branching. For example, strong branching might have proven that rounding up a variable would lead to an infeasible LP relaxation and thus, the variable must be rounded down. Therefore, the BRANCHEXECLP, BRANCHEXECPS and BRANCHEXECREL callbacks may also produce domain reductions or add additional constraints to the current subproblem.

The execution callbacks have the following options:

  • detecting that the node is infeasible and can be cut off (result SCIP_CUTOFF)
  • adding an additional constraint (e.g. a conflict constraint) (result SCIP_CONSADDED; note that this action must not be performed if the input "allowaddcons" is FALSE)
  • reducing the domain of a variable such that the current LP solution becomes infeasible (result SCIP_REDUCEDDOM)
  • applying a branching (result SCIP_BRANCHED)
  • stating that the branching rule was skipped (result SCIP_DIDNOTRUN).

Only the BRANCHEXECLP callback has the possibility to add a cutting plane to the LP (result SCIP_SEPARATED).

BRANCHFREE

If you are using branching rule data, you have to implement this method in order to free the branching rule data. This can be done by the following procedure:

static
SCIP_DECL_BRANCHFREE(branchFreeMybranchingrule)
{
SCIP_BRANCHRULEDATA* branchruledata;
branchruledata = SCIPbranchruleGetData(branchrule);
assert(branchruledata != NULL);
SCIPfreeMemory(scip, &branchruledata);
SCIPbranchruleSetData(branchrule, NULL);
return SCIP_OKAY;
}

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

BRANCHINIT

The BRANCHINIT callback is executed after the problem is transformed. The branching rule may, e.g., use this call to initialize its branching rule data.

BRANCHCOPY

The BRANCHCOPY 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 branching rule for all copied SCIP instances. This may deteriorate the performance of primal heuristics using sub-SCIPs.

BRANCHEXIT

The BRANCHEXIT callback is executed before the transformed problem is freed. In this method, the branching rule should free all resources that have been allocated for the solving process in BRANCHINIT.

BRANCHINITSOL

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

BRANCHEXITSOL

The BRANCHEXITSOL callback is executed before the branch-and-bound process is freed. The branching rule should use this call to clean up its branch-and-bound data.