source: html/ch03.html @ 2246

Last change on this file since 2246 was 561, checked in by ladanyi, 12 years ago

Cbc static pages moved

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.2 KB
Line 
1<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?>
2<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 3. 
3  Selecting the Next Node in the Search Tree
4  </title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2"/><link rel="home" href="index.html" title="CBC User Guide"/><link rel="up" href="index.html" title="CBC User Guide"/><link rel="previous" href="ch02s06.html" title="&#10;  Impacting the Solution Process&#10;  "/><link rel="next" href="ch04.html" title="Chapter 4. &#10;  Getting Good Bounds in CBC&#10;  "/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 3. 
5  Selecting the Next Node in the Search Tree
6  </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch02s06.html">Prev</a> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="ch04.html">Next</a></td></tr></table><hr/></div><div class="chapter" lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="otherclasses"/>Chapter 3. 
7  Selecting the Next Node in the Search Tree
8  </h2></div></div><div/></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="ch03.html#comparison">CbcCompare - Comparison Methods</a></dt></dl></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="comparison"/>CbcCompare - Comparison Methods</h2></div></div><div/></div><p>
9  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 <tt class="classname">CbcCompare...</tt> class, and its method <tt class="function">test()</tt>. Dynamic changes can be made whenever
10</p><div class="itemizedlist"><ul type="disc"><li>a new solution is found -- by customizing the method <tt class="function">newSolution()</tt>, or </li><li>every 1000 nodes -- by customizing the method <tt class="function">every1000Nodes()</tt>. </li></ul></div><p>
11CBC provides an abstract base class, <tt class="classname">CbcCompareBase</tt>, and implementations of several commonly used node selection strategies as Compare Classes, see <a href="ch03.html#compareTable" title="Table 3.1. Compare Classes Provided">Table 3.1</a>.
12  </p><div class="table"><a id="compareTable"/><p class="title"><b>Table 3.1. Compare Classes Provided</b></p><table summary="Compare Classes Provided" border="0"><colgroup><col/><col/></colgroup><thead><tr><th>
13    Class name
14    </th><th>
15    Description
16    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareDepth</tt></td><td align="left" valign="top">
17      This will always choose the node deepest in tree.  It gives minimum
18      tree size but may take a long time to find the best solution.
19      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareObjective</tt></td><td align="left" valign="top">
20      This will always choose the node with the best objective value.  This may
21      give a very large tree.  It is likely that the first solution found
22      will be the best and the search should finish soon after the first solution
23      is found.
24      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareDefault</tt></td><td align="left" valign="top">
25      This is designed to do a mostly depth-first search until a solution has
26      been found. It then use estimates that are designed to give a slightly better solution.
27      If a reasonable number of nodes have been explored (or a reasonable number of
28      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 <tt class="classname">CbcCompareUser</tt> is given below.
29      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareEstimate</tt></td><td align="left" valign="top">
30      When pseudo costs are invoked, CBC uses the psuedo costs to guess a solution.  This class uses the guessed solution.
31      </td></tr></tbody></table></div><p>
32  It is relatively simple for a user to create a customized node selection by creating a new compare class instances. The code in <a href="ch03.html#test" title="Example 3.1. CbcCompareUser::test()">Example 3.1</a> describes how to build a new comparison class and the reasoning behind it. The complete source can be found in <tt class="filename">CbcCompareUser.hpp</tt> and <tt class="filename">CbcCompareUser.cpp</tt>, located in the CBC Samples directory. Besides the constructor, the only method the user -must- implement in <tt class="classname">CbcCompare</tt> is <tt class="function">bool test(CbcNode* x, CbcNode* y))</tt> which returns <i class="parameter"><tt>true</tt></i> if node <i class="parameter"><tt>y</tt></i> is preferred over node <i class="parameter"><tt>x</tt></i>. In the <tt class="function">test()</tt> method, information from <tt class="classname">CbcNode</tt> can easily be used. <a href="ch03.html#nodeTable" title="Table 3.2. Information Available from CbcNode">Table 3.2</a> lists some commonly used methods to access information at a node.
33  </p><div class="table"><a id="nodeTable"/><p class="title"><b>Table 3.2. Information Available from <tt class="classname">CbcNode</tt></b></p><table summary="Information Available from CbcNode" border="0"><colgroup><col/><col/></colgroup><tbody><tr><td align="left" valign="top"><tt class="function">double objectiveValue() const</tt></td><td align="left" valign="top">
34      Value of objective at the node.
35      </td></tr><tr><td align="left" valign="top"><tt class="function">int numberUnsatisfied() const</tt></td><td align="left" valign="top">
36      Number of unsatisfied integers (assuming branching
37      object is an integer - otherwise it might be number of unsatisfied sets).
38      </td></tr><tr><td align="left" valign="top"><tt class="function">int depth() const</tt></td><td align="left" valign="top">
39       Depth of the node in the search tree.
40      </td></tr><tr><td align="left" valign="top"><tt class="function">double guessedObjectiveValue() const</tt></td><td align="left" valign="top"> 
41     Returns the guessed objective value, if the user was setting this (e.g., if using pseudo costs).
42      </td></tr><tr><td align="left" valign="top"><tt class="function">int way() const</tt></td><td align="left" valign="top">
43       The way which branching would next occur from this node
44       (for more advanced use).
45      </td></tr><tr><td align="left" valign="top"><tt class="function">int variable() const</tt></td><td align="left" valign="top">
46       The branching "variable" (associated with the <tt class="classname">CbcBranchingObject</tt> -- for more advanced use).
47      </td></tr></tbody></table></div><p>
48</p><p>
49The 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
50  <tt class="function">newSolution()</tt> is called whenever a solution is found and the method <tt class="function">every1000Nodes()</tt> is called every 1000 nodes.  When these methods are called, the user has the opportunity to modify the
51  behavior of <tt class="function">test()</tt> by adjusting their common variables (e.g., <tt class="varname">weight_</tt>). Because <tt class="classname">CbcNode</tt> 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., <tt class="function">CbcModel::setMaximumSeconds(double value)</tt>). In <tt class="filename">CbcCompareUser.cpp</tt> of the <tt class="filename">COIN/Cbc/Samples</tt> directory,  four items of data are used.
52</p><p>
53</p><div class="itemizedlist"><ul type="disc"><li><p>
541) The number of solutions found so far
55  </p></li><li><p>
562) The size of the tree (defined to be the number of active nodes)
57  </p></li><li><p>
583) A weight, <tt class="varname">weight_</tt>, which is initialized to -1.0
59  </p></li><li><p>
604) A saved value of weight, <tt class="varname">saveWeight_</tt> (for when weight is set back to -1.0 for special reason)
61  </p></li></ul></div><p>
62</p><p>
63Initially, <tt class="varname">weight</tt>_ is -1.0 and the search is biased towards depth first.  In
64fact, <tt class="function">test()</tt> prefers <i class="parameter"><tt>y</tt></i> if <i class="parameter"><tt>y</tt></i> has fewer unsatisfied variables. In the case of a tie, <tt class="function">test()</tt> prefers the node with the greater depth in tree. The full code for the <tt class="function">CbcCompareUser::test()</tt> method is given in <a href="ch03.html#test" title="Example 3.1. CbcCompareUser::test()">Example 3.1</a>.
65</p><div class="example"><a id="test"/><p class="title"><b>Example 3.1. <tt class="function">CbcCompareUser::test()</tt></b></p><pre class="programlisting">
66   
67// Returns true if y better than x
68bool
69CbcCompareUser::test (CbcNode * x, CbcNode * y)
70{
71  if (weight_==-1.0) {
72    // before solution
73    if (x-&gt;numberUnsatisfied() &gt; y-&gt;numberUnsatisfied())
74      return true;
75    else if (x-&gt;numberUnsatisfied() &lt; y-&gt;numberUnsatisfied())
76      return false;
77    else
78      return x-&gt;depth() &lt; y-&gt;depth();
79  } else {
80    // after solution.
81    // note: if weight_=0, comparison is based
82    //       solely on objective value
83    double weight = CoinMax(weight_,0.0);
84    return x-&gt;objectiveValue()+ weight*x-&gt;numberUnsatisfied() &gt; 
85      y-&gt;objectiveValue() + weight*y-&gt;numberUnsatisfied();
86  }
87}
88     
89  </pre></div><p>
90CBC calls the method <tt class="function">newSolution()</tt> after a new solution is found. The method <tt class="function">newSolution()</tt> interacts with <tt class="function">test()</tt> by means of the variable <tt class="varname">weight_</tt>. 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 <tt class="varname">weight_</tt> is then set to aim at a slightly better solution.  From then on, <tt class="function">test()</tt> returns <i class="parameter"><tt>true</tt></i> if it seems that <i class="parameter"><tt>y</tt></i> will lead to a better solution than <i class="parameter"><tt>x</tt></i>. This source for <tt class="function">newSolution()</tt> in given in <a href="ch03.html#newSolution" title="Example 3.2. CbcCompareUser::newSolution()">Example 3.2</a>.
91</p><div class="example"><a id="newSolution"/><p class="title"><b>Example 3.2. <tt class="function">CbcCompareUser::newSolution()</tt></b></p><pre class="programlisting">
92   
93// This allows the test() method to change behavior by resetting weight_.
94// It is called after each new solution is found.
95void
96CbcCompareUser::newSolution(CbcModel * model,
97                               double objectiveAtContinuous,
98                               int numberInfeasibilitiesAtContinuous)
99{
100  if (model-&gt;getSolutionCount()==model-&gt;getNumberHeuristicSolutions())
101    return; // The number of solutions found by any means equals the
102            // number of solutions, so this solution was found by rounding.
103            // Ignore it.
104
105  // set weight_ to get close to this solution
106  double costPerInteger =
107    (model-&gt;getObjValue()-objectiveAtContinuous)/
108    ((double) numberInfeasibilitiesAtContinuous);
109  weight_ = 0.98*costPerInteger; // this aims for a solution
110                                 // slightly better than known.
111                                 // why 0.98? why not?! Experiment yourself.                                 
112  saveWeight_=weight_; // We're going to switching between depth-first and breadth-first
113                       // branching strategies, depending on what we find in the tree.
114                       // When doing depth first, we'll want to retrieve this weight.
115                       // So, let's save it.
116  numberSolutions_++;
117  if (numberSolutions_&gt;5)
118    weight_ =0.0; // comparison in test() will be
119                  // based strictly on objective value.
120}
121     
122  </pre></div><p>
123
124As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been generated, then <tt class="varname">weight_</tt> 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 <tt class="function">every1000Nodes</tt> shown in <a href="ch03.html#everyK" title="Example 3.3. CbcCompareUser::every1000Nodes()">Example 3.3</a>.
125  </p><div class="example"><a id="everyK"/><p class="title"><b>Example 3.3. <tt class="function">CbcCompareUser::every1000Nodes()</tt></b></p><pre class="programlisting">
126   
127// This allows the test() method to change behavior every 1000 nodes.
128bool
129CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
130{
131  if (numberNodes&gt;10000)
132    weight_ =0.0; // compare nodes based on objective value
133    // get size of tree
134  treeSize_ = model-&gt;tree()-&gt;size();
135  if (treeSize_&gt;10000) {
136    // set weight to reduce size most of time
137    if (treeSize_&gt;20000)
138      weight_=-1.0;
139    else if ((numberNodes%4000)!=0)  // Flip-flop between the strategies.
140                                     // Why 4000? Why not? Experiment yourself.
141      weight_=-1.0;
142    else
143      weight_=saveWeight_;
144  }
145  return numberNodes==11000; // resort if first time
146}
147     
148  </pre></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch02s06.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="index.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch04.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">
149  Impacting the Solution Process
150   </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 4. 
151  Getting Good Bounds in CBC
152  </td></tr></table></div></body></html>
Note: See TracBrowser for help on using the repository browser.