Chapter 3.  Selecting the Next Node in the Search Tree

The order in which the nodes of the search tree are explored can strongly influence the performance of branch-and-cut algorithms. CBC give users complete control over the search order, including the ability to dynamically change the node selection logic as the search progresses. The search order is controlled via the CbcCompare... class, and its method test(). Dynamic changes can be made whenever

CBC provides an abstract base class, CbcCompareBase, and implementations of several commonly used node selection strategies as Compare Classes, see Table 3.1.

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.

The node desired in the tree is often a function of the how the search is progressing. In the design of CBC, there is no information on the state of the tree. The CBC is designed so that the method newSolution() is called whenever a solution is found and the method every1000Nodes() is called every 1000 nodes. When these methods are called, the user has the opportunity to modify the behavior of test() by adjusting their common variables (e.g., weight_). Because CbcNode has a pointer to the model, the user can also influence the search through actions such as changing the maximum time CBC is allowed, once a solution has been found (e.g., CbcModel::setMaximumSeconds(double value)). In CbcCompareUser.cpp of the COIN/Cbc/Samples directory, four items of data are used.

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.