Table of Contents
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.
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). |
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.
1) The number of solutions found so far
2) The size of the tree (defined to be the number of active nodes)
3) A weight, weight_, which is initialized to -1.0
4) A saved value of weight, saveWeight_ (for when weight is set back to -1.0 for special reason)
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.
Example 3.1. CbcCompareUser::test()
// Returns true if y better than x bool CbcCompareUser::test (CbcNode * x, CbcNode * y) { if (weight_==-1.0) { // before solution if (x->numberUnsatisfied() > y->numberUnsatisfied()) return true; else if (x->numberUnsatisfied() < y->numberUnsatisfied()) return false; else return x->depth() < y->depth(); } else { // after solution. // note: if weight_=0, comparison is based // solely on objective value double weight = CoinMax(weight_,0.0); return x->objectiveValue()+ weight*x->numberUnsatisfied() > y->objectiveValue() + weight*y->numberUnsatisfied(); } }
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.
Example 3.2. CbcCompareUser::newSolution()
// This allows the test() method to change behavior by resetting weight_. // It is called after each new solution is found. void CbcCompareUser::newSolution(CbcModel * model, double objectiveAtContinuous, int numberInfeasibilitiesAtContinuous) { if (model->getSolutionCount()==model->getNumberHeuristicSolutions()) return; // The number of solutions found by any means equals the // number of solutions, so this solution was found by rounding. // Ignore it. // set weight_ to get close to this solution double costPerInteger = (model->getObjValue()-objectiveAtContinuous)/ ((double) numberInfeasibilitiesAtContinuous); weight_ = 0.98*costPerInteger; // this aims for a solution // slightly better than known. // why 0.98? why not?! Experiment yourself. saveWeight_=weight_; // We're going to switching between depth-first and breadth-first // branching strategies, depending on what we find in the tree. // When doing depth first, we'll want to retrieve this weight. // So, let's save it. numberSolutions_++; if (numberSolutions_>5) weight_ =0.0; // comparison in test() will be // based strictly on objective value. }
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.
Example 3.3. CbcCompareUser::every1000Nodes()
// This allows the test() method to change behavior every 1000 nodes. bool CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes) { if (numberNodes>10000) weight_ =0.0; // compare nodes based on objective value // get size of tree treeSize_ = model->tree()->size(); if (treeSize_>10000) { // set weight to reduce size most of time if (treeSize_>20000) weight_=-1.0; else if ((numberNodes%4000)!=0) // Flip-flop between the strategies. // Why 4000? Why not? Experiment yourself. weight_=-1.0; else weight_=saveWeight_; } return numberNodes==11000; // resort if first time }