source: branches/gh-pages/nodeselection.md

Last change on this file was 2522, checked in by stefan, 8 months ago

reproduce r558 and r559

  • Property svn:eol-style set to native
File size: 9.8 KB
Line 
1# Selecting the Next Node in the Search Tree
2
3## CbcCompare - Comparison Methods
4
5The order in which the nodes of the search tree are explored can
6strongly influence the performance of branch-and-cut algorithms. CBC
7give users complete control over the search order. The search order is
8controlled via the `CbcCompare...` class. CBC provides an abstract base
9class, `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
18It is relatively simple for an experienced user to create new compare
19class instances. The code in the example below describes how to
20build a new comparison class and the reasoning behind it. The complete
21source can be found in `CbcCompareUser.hpp` and `CbcCompareUser.cpp`,
22located in the CBC Samples directory. The key
23method in `CbcCompare` is `bool test(CbcNode* x, CbcNode* y))` which
24returns `true` if node `y` is preferred over node `x`. In the `test()`
25method, information from `CbcNode` can easily be used.
26The following table lists some commonly used methods to access
27information 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
38The node desired in the tree is often a function of the how the search
39is progressing. In the design of CBC, there is no information on the
40state 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
43called, the user has the opportunity to modify the behavior of `test()`
44by adjusting their common variables (e.g., `weight_`). Because `CbcNode`
45has a pointer to the model, the user can also influence the search
46through actions such as changing the maximum time CBC is allowed, once a
47solution has been found (e.g., `CbcModel::setMaximumSeconds(double
48value)`). In `CbcCompareUser.cpp` of the `Cbc/examples` directory,
49four 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
56The full code for the `CbcCompareUser::test()` method is the following:
57
58```
59// Returns true if y better than x
60bool
61CbcCompareUser::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
82Initially, `weight`\_ is -1.0 and the search is biased towards depth
83first. In fact, `test()` prefers `y` if `y` has fewer unsatisfied
84variables. In the case of a tie, `test()` prefers the node with the
85greater depth in tree. Once a solution is found, `newSolution()` is
86called. The method `newSolution()` interacts with `test()` by means of
87the variable `weight_`. If the solution was achieved by branching, a
88calculation is made to determine the cost per unsatisfied integer
89variable to go from the continuous solution to an integer solution. The
90variable `weight_` is then set to aim at a slightly better solution.
91From then on, `test()` returns `true` if it seems that `y` will lead to
92a 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.
97void
98CbcCompareUser::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
118As 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
120leading to a breadth-first search. Breadth-first search can lead to an
121enormous tree. If the tree size is exceeds 10000, it may be desirable to
122return to a search biased towards depth first. Changing the behavior in
123this manner is done by the method `every1000Nodes` shown next:
124
125```
126// This allows the test() method to change behavior every so often
127bool
128CbcCompareUser::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```
Note: See TracBrowser for help on using the repository browser.