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` | Returns the guessed objective value, if the 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 | ``` |
---|