source: html/trunk/Cbc/ch03.html @ 554

Last change on this file since 554 was 554, checked in by rlh, 16 years ago

initial import of Cbc documentation

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.0 KB
Line 
1<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Chapter 3. 
2  Other Classes and examples
3  </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="ch02s05.html" title="
4  Methods which have a major impact on solution process
5  "><link rel="next" href="ch03s02.html" title="CbcHeuristic - heuristic methods"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 3. 
6  Other Classes and examples
7  </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch02s05.html">Prev</a> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="ch03s02.html">Next</a></td></tr></table><hr></div><div class="chapter" lang="en"><div class="titlepage"><div><div><h2 class="title"><a name="otherclasses"></a>Chapter 3. 
8  Other Classes and examples
9  </h2></div></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><dt><a href="ch03s02.html">CbcHeuristic - heuristic methods</a></dt><dt><a href="ch03s03.html">Branching</a></dt><dt><a href="ch03s04.html">Advanced use of solver</a></dt></dl></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="comparison"></a>CbcCompare - Comparison methods</h2></div></div><div></div></div><p>
10  Although the unexplored nodes of the search are organized in a tree, the
11  order of solution is not predetermined and can be influenced by the user.
12  Cbc provides a abstract base class CbcCompareBase
13  and then instances of each.  It is relatively simple for an advanced user to
14  create new instances and an explanation of an example will be given later.
15  </p><div class="table"><a name="id2901322"></a><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>
16    Class name
17    </th><th>
18    Description
19    </th></tr></thead><tbody><tr><td align="left" valign="top">
20      CbcCompareDepth
21      </td><td align="left" valign="top">
22      This will always choose the node deepest in tree.  It gives minimum
23      tree size but may take a long time to find best solution.
24      </td></tr><tr><td align="left" valign="top">
25      CbcCompareObjective
26      </td><td align="left" valign="top">
27      This will always choose the node with the best objective value.  This may
28      give a very large tree.  It is likely that the first solution found
29      will be the best and the search should finish soon after the first solution
30      is found.
31      </td></tr><tr><td align="left" valign="top">
32      CbcCompareDefault
33      </td><td align="left" valign="top">
34      This is designed to do a mostly depth first search until a solution has
35      been found and then use estimates designed to give a slightly better solution.
36      If a reasonable number of nodes have been done or a reasonable number of
37      solutions found then it will go breadth first (i.e. on objective) unless
38      the tree is very large when it will revert to depth first.  Probably
39      CbcCompareUser described below is better.
40      </td></tr><tr><td align="left" valign="top">
41      CbcCompareEstimate
42      </td><td align="left" valign="top">
43      If pseudocosts are being used then they can be used to guess a solution.
44      This just uses guessed solution.
45      </td></tr></tbody></table></div><p>
46  This describes how to build a new comparison class and the reasoning
47  behind it. This is <tt class="filename">CbcCompareUser.hpp</tt> and
48   <tt class="filename">CbcCompareUser.cpp</tt>
49  (this code can be found in the CBC Samples directory, see
50  <a href="ch05.html" title="Chapter 5. 
51More Samples
52">Chapter 5, <i>
53More Samples
54</i></a>).
55  The key CbcCompare method is test which returns true if node y is better
56  than node x.  In this method the user can easily use
57  </p><div class="table"><a name="id2902562"></a><p class="title"><b>Table 3.2. Information available from CbcModel</b></p><table summary="Information available from CbcModel" border="0"><colgroup><col><col></colgroup><tbody><tr><td align="left" valign="top">
58      objectiveValue()
59      </td><td align="left" valign="top">
60      Value of objective at that node.
61      </td></tr><tr><td align="left" valign="top">
62      numberUnsatisfied()
63      </td><td align="left" valign="top">
64      Number of unsatisfied integers (assuming branching
65      object is an integer - otherwise might be number of unsatsified sets)
66      </td></tr><tr><td align="left" valign="top">
67      depth()
68      </td><td align="left" valign="top">
69       depth in tree of node
70      </td></tr><tr><td align="left" valign="top">
71      guessedObjectiveValue()
72      </td><td align="left" valign="top"> </td></tr><tr><td align="left" valign="top">
73      way()   
74      </td><td align="left" valign="top">
75       which way would be next from this node
76       (for more advanced use)
77      </td></tr><tr><td align="left" valign="top">
78      variable()
79      </td><td align="left" valign="top">
80       which "variable" would be branched on.
81       (for more advanced use)
82      </td></tr></tbody></table></div><p>
83  </p><p>
84  There is no information on the state of the tree.  If you wanted you could
85  keep a pointer to the CbcModel but the way it is meant to work is that
86  newSolution is called whenever a solution is found and every1000Nodes is
87  called every 1000 nodes.  When these are called the user can modify the
88  behavior of test.  Because the model is passed in the user can also do other things
89  such as changing the maximum time of Branch and Cut once a solution has been found.
90
91So in CbcCompareUser in Samples
92the four items of data are:
931) The number of solutions found so far
942) The size of the tree (number of active nodes)
953) A weight which is initialized to -1.0
964) A saved value of weight (for when we set weight back to -1.0 for special reason)
97
98The full code for test is:
99</p><div class="example"><a name="id2902771"></a><p class="title"><b>Example 3.1. test</b></p><pre class="programlisting">
100   
101// Returns true if y better than x
102bool
103CbcCompareUser::test (CbcNode * x, CbcNode * y)
104{
105  if (weight_==-1.0) {
106    // before solution
107    if (x-&gt;numberUnsatisfied() &gt; y-&gt;numberUnsatisfied())
108      return true;
109    else if (x-&gt;numberUnsatisfied() &lt; y-&gt;numberUnsatisfied())
110      return false;
111    else
112      return x-&gt;depth() &lt; y-&gt;depth();
113  } else {
114    // after solution
115    double weight = CoinMax(weight_,0.0);
116    return x-&gt;objectiveValue()+ weight*x-&gt;numberUnsatisfied() &gt; 
117      y-&gt;objectiveValue() + weight*y-&gt;numberUnsatisfied();
118  }
119}
120     
121  </pre></div><p>
122So initially as weight is &lt; 0.0 we are biased towards depth first.  In
123fact it prefers y is y has fewer unsatisfied variables - if there is a tie
124then it prefers the one with greater depth in tree.
125
126Once we get a solution newSolution is called.  If it was a solution
127achieved by branching we work out how much it cost per unsatisfied integer
128variable to go from continuous solution to integer solution.  We then set
129the weight to aim at a slightly better solution.  From then on test
130returns true if it looks as if y will lead to a better solution than x.
131This is done by newSolution
132</p><div class="example"><a name="id2902794"></a><p class="title"><b>Example 3.2. newSolution</b></p><pre class="programlisting">
133   
134// This allows method to change behavior as it is called
135// after each solution
136void
137CbcCompareUser::newSolution(CbcModel * model,
138                               double objectiveAtContinuous,
139                               int numberInfeasibilitiesAtContinuous)
140{
141  if (model-&gt;getSolutionCount()==model-&gt;getNumberHeuristicSolutions())
142    return; // solution was got by rounding so we ignore
143  // set to get close to this solution
144  double costPerInteger =
145    (model-&gt;getObjValue()-objectiveAtContinuous)/
146    ((double) numberInfeasibilitiesAtContinuous);
147  weight_ = 0.98*costPerInteger;
148  saveWeight_=weight_;
149  numberSolutions_++;
150  if (numberSolutions_&gt;5)
151    weight_ =0.0; // this searches on objective
152}
153     
154  </pre></div><p>
155
156But as the search goes on this may be modified.
157
158If we have done a lot of nodes or got a lot of solutions then weight is
159set to 0.0 so we are doing breadth first search.  This can lead to an
160enormous tree so if the tree size is &gt;10000 then we go may go back to one biased
161towards depth first.  This is done by every1000Nodes.
162  </p><div class="example"><a name="id2902874"></a><p class="title"><b>Example 3.3. newSolution</b></p><pre class="programlisting">
163   
164// This allows method to change behavior
165bool
166CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
167{
168  if (numberNodes&gt;10000)
169    weight_ =0.0; // this searches on objective
170  else if (numberNodes==1000&amp;&amp;weight_==-2.0)
171    weight_=-1.0; // Go to depth first
172  // get size of tree
173  treeSize_ = model-&gt;tree()-&gt;size();
174  if (treeSize_&gt;10000) {
175    // set weight to reduce size most of time
176    if (treeSize_&gt;20000)
177      weight_=-1.0;
178    else if ((numberNodes%4000)!=0)
179      weight_=-1.0;
180    else
181      weight_=saveWeight_;
182  }
183  return numberNodes==11000; // resort if first time
184}
185     
186  </pre></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch02s05.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="ch03s02.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">
187  Methods which have a major impact on solution process
188   </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> CbcHeuristic - heuristic methods</td></tr></table></div></body></html>
Note: See TracBrowser for help on using the repository browser.