[2521] | 1 | # Selecting the Next Node in the Search Tree |
---|
| 2 | |
---|
| 3 | ## CbcCompare - Comparison Methods |
---|
| 4 | |
---|
| 5 | The order in which the nodes of the search tree are explored can |
---|
| 6 | strongly influence the performance of branch-and-cut algorithms. CBC |
---|
| 7 | give users complete control over the search order. The search order is |
---|
| 8 | controlled via the `CbcCompare...` class. CBC provides an abstract base |
---|
| 9 | class, `CbcCompareBase`, and several commonly used instances: |
---|
| 10 | |
---|
| 11 | | Class name | Description | |
---|
| 12 | | --------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | |
---|
| 13 | | `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. | |
---|
| 14 | | `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. | |
---|
| 15 | | `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 when it will revert to depth-first search. A better description of `CbcCompareUser` is given below. | |
---|
| 16 | | `CbcCompareEstimate` | When pseudo costs are invoked, they can be used to guess a solution. This class uses the guessed solution. | |
---|
| 17 | |
---|
| 18 | It is relatively simple for an experienced user to create new compare |
---|
| 19 | class instances. The code in the example below describes how to |
---|
| 20 | build a new comparison class and the reasoning behind it. The complete |
---|
| 21 | source can be found in `CbcCompareUser.hpp` and `CbcCompareUser.cpp`, |
---|
| 22 | located in the CBC Samples directory. The key |
---|
| 23 | method in `CbcCompare` is `bool test(CbcNode* x, CbcNode* y))` which |
---|
| 24 | returns `true` if node `y` is preferred over node `x`. In the `test()` |
---|
| 25 | method, information from `CbcNode` can easily be used. |
---|
| 26 | The following table lists some commonly used methods to access |
---|
| 27 | information at a node. |
---|
| 28 | |
---|
| 29 | | Method Name | Description | |
---|
| 30 | | -------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------- | |
---|
| 31 | | `double objectiveValue() const` | Value of objective at the node. | |
---|
| 32 | | `int numberUnsatisfied() const` | Number of unsatisfied integers (assuming branching object is an integer - otherwise it might be number of unsatisfied sets). | |
---|
| 33 | | `int depth() const` | Depth of the node in the search tree. | |
---|
| 34 | | `double guessedObjectiveValue() const` | If user was setting this (e.g., if using pseudo costs). | |
---|
| 35 | | `int way() const` | The way which branching would next occur from this node (for more advanced use). | |
---|
| 36 | | `int variable() const` | The branching "variable" (associated with the `CbcBranchingObject` -- for more advanced use). | |
---|
| 37 | |
---|
| 38 | The node desired in the tree is often a function of the how the search |
---|
| 39 | is progressing. In the design of CBC, there is no information on the |
---|
| 40 | state of the tree. CBC is designed so that the method |
---|
| 41 | `newSolution()` is called whenever a solution is found and the method |
---|
| 42 | `every1000Nodes()` is called every 1000 nodes. When these methods are |
---|
| 43 | called, the user has the opportunity to modify the behavior of `test()` |
---|
| 44 | by adjusting their common variables (e.g., `weight_`). Because `CbcNode` |
---|
| 45 | has a pointer to the model, the user can also influence the search |
---|
| 46 | through actions such as changing the maximum time CBC is allowed, once a |
---|
| 47 | solution has been found (e.g., `CbcModel::setMaximumSeconds(double |
---|
| 48 | value)`). In `CbcCompareUser.cpp` of the `Cbc/examples` directory, |
---|
| 49 | four items of data are used. |
---|
| 50 | |
---|
| 51 | 1. The number of solutions found so far |
---|
| 52 | 2. The size of the tree (defined to be the number of active nodes) |
---|
| 53 | 3. A weight, `weight_`, which is initialized to -1.0 |
---|
| 54 | 4. A saved value of weight, `saveWeight_` (for when weight is set back to -1.0 for special reason) |
---|
| 55 | |
---|
| 56 | The full code for the `CbcCompareUser::test()` method is the following: |
---|
| 57 | |
---|
| 58 | ``` |
---|
| 59 | // Returns true if y better than x |
---|
| 60 | bool |
---|
| 61 | CbcCompareUser::test (CbcNode * x, CbcNode * y) |
---|
| 62 | { |
---|
| 63 | if (weight_==-1.0) { |
---|
| 64 | // before solution |
---|
| 65 | if (x->numberUnsatisfied() > y->numberUnsatisfied()) |
---|
| 66 | return true; |
---|
| 67 | else if (x->numberUnsatisfied() < y->numberUnsatisfied()) |
---|
| 68 | return false; |
---|
| 69 | else |
---|
| 70 | return x->depth() < y->depth(); |
---|
| 71 | } else { |
---|
| 72 | // after solution. |
---|
| 73 | // note: if weight_=0, comparison is based |
---|
| 74 | // solely on objective value |
---|
| 75 | double weight = CoinMax(weight_,0.0); |
---|
| 76 | return x->objectiveValue()+ weight*x->numberUnsatisfied() > |
---|
| 77 | y->objectiveValue() + weight*y->numberUnsatisfied(); |
---|
| 78 | } |
---|
| 79 | } |
---|
| 80 | ``` |
---|
| 81 | |
---|
| 82 | Initially, `weight`\_ is -1.0 and the search is biased towards depth |
---|
| 83 | first. In fact, `test()` prefers `y` if `y` has fewer unsatisfied |
---|
| 84 | variables. In the case of a tie, `test()` prefers the node with the |
---|
| 85 | greater depth in tree. Once a solution is found, `newSolution()` is |
---|
| 86 | called. The method `newSolution()` interacts with `test()` by means of |
---|
| 87 | the variable `weight_`. If the solution was achieved by branching, a |
---|
| 88 | calculation is made to determine the cost per unsatisfied integer |
---|
| 89 | variable to go from the continuous solution to an integer solution. The |
---|
| 90 | variable `weight_` is then set to aim at a slightly better solution. |
---|
| 91 | From then on, `test()` returns `true` if it seems that `y` will lead to |
---|
| 92 | a better solution than `x`. This source for `newSolution()` is the following: |
---|
| 93 | |
---|
| 94 | ``` |
---|
| 95 | // This allows the test() method to change behavior by resetting weight_. |
---|
| 96 | // It is called after each new solution is found. |
---|
| 97 | void |
---|
| 98 | CbcCompareUser::newSolution(CbcModel * model, |
---|
| 99 | double objectiveAtContinuous, |
---|
| 100 | int numberInfeasibilitiesAtContinuous) |
---|
| 101 | { |
---|
| 102 | if (model->getSolutionCount()==model->getNumberHeuristicSolutions()) |
---|
| 103 | return; // solution was found by rounding so ignore it. |
---|
| 104 | |
---|
| 105 | // set weight_ to get close to this solution |
---|
| 106 | double costPerInteger = |
---|
| 107 | (model->getObjValue()-objectiveAtContinuous)/ |
---|
| 108 | ((double) numberInfeasibilitiesAtContinuous); |
---|
| 109 | weight_ = 0.98*costPerInteger; |
---|
| 110 | saveWeight_=weight_; |
---|
| 111 | numberSolutions_++; |
---|
| 112 | if (numberSolutions_>5) |
---|
| 113 | weight_ =0.0; // comparison in test() will be |
---|
| 114 | // based strictly on objective value. |
---|
| 115 | } |
---|
| 116 | ``` |
---|
| 117 | |
---|
| 118 | As the search progresses, the comparison can be modified. If many nodes |
---|
| 119 | (or many solutions) have been generated, then `weight_` is set to 0.0 |
---|
| 120 | leading to a breadth-first search. Breadth-first search can lead to an |
---|
| 121 | enormous tree. If the tree size is exceeds 10000, it may be desirable to |
---|
| 122 | return to a search biased towards depth first. Changing the behavior in |
---|
| 123 | this manner is done by the method `every1000Nodes` shown next: |
---|
| 124 | |
---|
| 125 | ``` |
---|
| 126 | // This allows the test() method to change behavior every so often |
---|
| 127 | bool |
---|
| 128 | CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes) |
---|
| 129 | { |
---|
| 130 | if (numberNodes>10000) |
---|
| 131 | weight_ =0.0; // compare nodes based on objective value |
---|
| 132 | else if (numberNodes==1000&&weight_==-2.0) |
---|
| 133 | weight_=-1.0; // Go to depth first |
---|
| 134 | // get size of tree |
---|
| 135 | treeSize_ = model->tree()->size(); |
---|
| 136 | if (treeSize_>10000) { |
---|
| 137 | // set weight to reduce size most of time |
---|
| 138 | if (treeSize_>20000) |
---|
| 139 | weight_=-1.0; |
---|
| 140 | else if ((numberNodes%4000)!=0) |
---|
| 141 | weight_=-1.0; |
---|
| 142 | else |
---|
| 143 | weight_=saveWeight_; |
---|
| 144 | } |
---|
| 145 | return numberNodes==11000; // resort if first time |
---|
| 146 | } |
---|
| 147 | ``` |
---|