CBC provides an abstract base class, CbcCompareBase, and implementations of several commonly used node selection strategies as Compare Classes, see Table 3.1.
Table 3.1. Compare Classes Provided
Class name | Description |
---|---|
CbcCompareDepth | This will always choose the node deepest in tree. It gives minimum tree size but may take a long time to find the best solution. |
CbcCompareObjective | This will always choose the node with the best objective value. This may give a very large tree. It is likely that the first solution found will be the best and the search should finish soon after the first solution is found. |
CbcCompareDefault | This is designed to do a mostly depth-first search until a solution has been found. It then use estimates that are designed to give a slightly better solution. If a reasonable number of nodes have been explored (or a reasonable number of solutions found), then this class will adopt a breadth-first search (i.e., making a comparison based strictly on objective function values) unless the tree is very large, in which case it will revert to depth-first search. A better description of CbcCompareUser is given below. |
CbcCompareEstimate | When pseudo costs are invoked, CBC uses the psuedo costs to guess a solution. This class uses the guessed solution. |
It is relatively simple for a user to create a customized node selection by creating a new compare class instances. The code in Example 3.1 describes how to build a new comparison class and the reasoning behind it. The complete source can be found in CbcCompareUser.hpp and CbcCompareUser.cpp, located in the CBC Samples directory. Besides the constructor, the only method the user -must- implement in CbcCompare is bool test(CbcNode* x, CbcNode* y)) which returns true if node y is preferred over node x. In the test() method, information from CbcNode can easily be used. Table 3.2 lists some commonly used methods to access information at a node.
Table 3.2. Information Available from CbcNode
double objectiveValue() const | Value of objective at the node. |
int numberUnsatisfied() const | Number of unsatisfied integers (assuming branching object is an integer - otherwise it might be number of unsatisfied sets). |
int depth() const | Depth of the node in the search tree. |
double guessedObjectiveValue() const | Returns the guessed objective value, if the user was setting this (e.g., if using pseudo costs). |
int way() const | The way which branching would next occur from this node (for more advanced use). |
int variable() const | The branching "variable" (associated with the CbcBranchingObject -- for more advanced use). |
Initially, weight_ is -1.0 and the search is biased towards depth first. In fact, test() prefers y if y has fewer unsatisfied variables. In the case of a tie, test() prefers the node with the greater depth in tree. The full code for the CbcCompareUser::test() method is given in Example 3.1.
CBC calls the method newSolution() after a new solution is found. The method newSolution() interacts with test() by means of the variable weight_. If the solution was achieved by branching, a calculation is made to determine the cost per unsatisfied integer variable to go from the continuous solution to an integer solution. The variable weight_ is then set to aim at a slightly better solution. From then on, test() returns true if it seems that y will lead to a better solution than x. This source for newSolution() in given in Example 3.2.
As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been generated, then weight_ is set to 0.0 leading to a breadth-first search. Breadth-first search can lead to an enormous tree. If the tree size is exceeds 10000, it may be desirable to return to a search biased towards depth first. Changing the behavior in this manner is done by the method every1000Nodes shown in Example 3.3.