source: html/cbcuserguide.html @ 818

Last change on this file since 818 was 561, checked in by ladanyi, 14 years ago

Cbc static pages moved
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 106.6 KB
Line 
1<?xml version="1.0" encoding="UTF-8"?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>CBC User Guide</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2" /></head><body><div class="book" lang="en" xml:lang="en"><div class="titlepage"><div><div><h1 class="title"><a id="cbcuserguide"></a>CBC User Guide</h1></div><div><div class="authorgroup"><div class="author"><h3 class="author"><span class="firstname">
4    John
5    </span> <span class="surname">
6    Forrest
7    </span></h3><div class="affiliation"><span class="orgname">
8      IBM Research
9      <br /></span></div></div><div class="author"><h3 class="author"><span class="firstname">
10    Robin
11    </span> <span class="surname">
12    Lougee-Heimer
13    </span></h3><div class="affiliation"><span class="orgname">
14      IBM Research
15      <br /></span></div></div></div></div><div><p class="copyright">Copyright © 2005 IBM Coportation</p></div><div><div class="legalnotice">
16CBC and this documentation are provided under the terms of the
17<a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public License
18 ("CPL")</a>.  Any use, reproduction or distribution of the programs constitutes
19the recipient's acceptance of the license.  The
20<a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a> is approved by
21the <a href="http://opensource.org/" target="_top">Open Source Initiative</a>.  IBM
22Corporation, the author of the
23<a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a>, has a
24<a href="http://www.ibm.com/developerworks/library/os-cplfaq.html" target="_top">
25CPL FAQ</a> available which is based on IBM's understanding of the
26<a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a>.
27</div></div></div><div></div><hr /></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt>1. <a href="#intro">
28    Introduction
29  </a></dt><dd><dl><dt><a href="#id3342315">
30  Welcome to CBC
31  </a></dt><dt><a href="#id3342145">
32  Prerequisites
33  </a></dt><dt><a href="#id3342019">Preliminaries</a></dt><dt><a href="#id3413036">
34Branch-and-Cut Overview
35</a></dt></dl></dd><dt>2. <a href="#cbcmodelclass">
36   The CBC Model Class
37  </a></dt><dd><dl><dt><a href="#hierarchy">
38  Overview
39  </a></dt><dt><a href="#firstexample">
40  Simple Branch-and-Bound Example
41  </a></dt><dt><a href="#osiAndCbc">
42The Relationship Between OSI and CBC
43</a></dt><dt><a href="#gettingsolution">
44  Getting Solution Information
45  </a></dt><dt><a href="#setsandgets">
46   Useful Set and Get Methods in CbcModel
47  </a></dt><dt><a href="#majormethods">
48  Impacting the Solution Process
49  </a></dt></dl></dd><dt>3. <a href="#otherclasses">
50  Selecting the Next Node in the Search Tree
51  </a></dt><dd><dl><dt><a href="#comparison">CbcCompare - Comparison Methods</a></dt></dl></dd><dt>4. <a href="#hueristicChap">
52  Getting Good Bounds in CBC
53  </a></dt><dd><dl><dt><a href="#heuristics">CbcHeuristic - Heuristic Methods</a></dt></dl></dd><dt>5. <a href="#branchChapter">
54  Branching
55 </a></dt><dd><dl><dt><a href="#branchingIntro">Branching Overview</a></dt><dt><a href="#branching">Pseudo Cost Branching</a></dt><dt><a href="#followOn">Follow-On Branching</a></dt></dl></dd><dt>6. <a href="#CutsChap">Cutting planes</a></dt><dd><dl><dt><a href="#cuts">Using Cut Generators with CBC</a></dt></dl></dd><dt>7. <a href="#SolverChap">
56  Advanced Solver Uses
57</a></dt><dd><dl><dt><a href="#solver">Creating a Solver via Inheritance</a></dt><dt><a href="#quadratic">Quadratic MIP</a></dt></dl></dd><dt>8. <a href="#moreexamples">
58More Samples
59</a></dt><dd><dl><dt><a href="#id3423737">CBC's Samples Directory</a></dt></dl></dd><dt>9. <a href="#messages">
60  Messages
61  </a></dt><dt>A. <a href="#id3430230">FAQ</a></dt><dt>B. <a href="#doxygen">Doxygen</a></dt><dt>C. <a href="#id3429980">Revision History</a></dt></dl></div><div class="list-of-tables"><p><b>List of Tables</b></p><dl><dt>1.1. <a href="#assClasses">Associated Classes</a></dt><dt>2.1. <a href="#id3415008">
62  Methods for Getting Solution Information from OSI
63  </a></dt><dt>2.2. <a href="#setGet">Useful Set and Get Methods in CbcModel</a></dt><dt>2.3. <a href="#id3416491">Classes Used by CbcModel - Most Useful</a></dt><dt>2.4. <a href="#least">Classes Used by CbcModel - Least Useful</a></dt><dt>3.1. <a href="#compareTable">Compare Classes Provided</a></dt><dt>3.2. <a href="#nodeTable">Information Available from CbcNode</a></dt><dt>8.1. <a href="#id3424694">Basic Samples</a></dt><dt>8.2. <a href="#id3424869">Advanced Samples</a></dt><dt>9.1. <a href="#id3426171">
64  CBC Messages Passed At Log Level 0
65  </a></dt><dt>9.2. <a href="#id3426316">
66  CBC Messages Passed At or Above Log Level 1
67  </a></dt><dt>9.3. <a href="#id3427680">
68  CBC Messages Passed At or Above Log Level 2
69  </a></dt><dt>9.4. <a href="#id3428080">
70  CBC Messages Passed At or Above Log Level 3
71  </a></dt></dl></div><div class="list-of-examples"><p><b>List of Examples</b></p><dl><dt>2.1. <a href="#minimum.cpp">minimum.cpp</a></dt><dt>3.1. <a href="#test">CbcCompareUser::test()</a></dt><dt>3.2. <a href="#newSolution">CbcCompareUser::newSolution()</a></dt><dt>3.3. <a href="#everyK">CbcCompareUser::every1000Nodes()</a></dt><dt>4.1. <a href="#id3421313">Data</a></dt><dt>4.2. <a href="#id3421342">Initialize newSolution</a></dt><dt>4.3. <a href="#id3421423">Create Feasible newSolution from Initial newSolution</a></dt><dt>4.4. <a href="#id3421467">Check Solution Quality of newSolution</a></dt><dt>5.1. <a href="#pseudo">CbcSimpleIntegerPseudoCosts</a></dt><dt>5.2. <a href="#id3421836">CbcFollowOn</a></dt><dt>7.1. <a href="#initialSolve">initialSolve()</a></dt><dt>7.2. <a href="#id3422104">First Few Solves</a></dt><dt>7.3. <a href="#id3422132">Create Small Sub-Problem</a></dt><dt>7.4. <a href="#id3422178">Check Optimal Solution</a></dt><dt>7.5. <a href="#id3422245">Solving a Quadratic MIP</a></dt></dl></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="intro"></a>Chapter 1. 
72    Introduction
73  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#id3342315">
74  Welcome to CBC
75  </a></dt><dt><a href="#id3342145">
76  Prerequisites
77  </a></dt><dt><a href="#id3342019">Preliminaries</a></dt><dt><a href="#id3413036">
78Branch-and-Cut Overview
79</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3342315"></a>
80  Welcome to CBC
81  </h2></div></div><div></div></div><p>
82  The COIN
83    <sup>[<a id="id3342326" href="#ftn.id3342326">1</a>]</sup>
84Branch and Cut solver (CBC) is an open-source mixed-integer program (MIP) solver written  in C++. CBC is intended to be used primarily as a callable library to create customized branch-and-cut solvers. A basic, stand-alone  executable version is also available. CBC is an active open-source project led by John Forrest at www.coin-or.org.
85 </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3342145"></a>
86  Prerequisites
87  </h2></div></div><div></div></div><p>
88  The primary users of CBC are expected to be developers implementing customized branch-and-cut algorithms in C++ using CBC as a library. Consequently, this document assumes a working knowledge of
89  <a href="http://www.cplusplus.com/doc/tutorial/" target="_top">C++</a>, including basic
90  object-oriented programming terminology, and familiarity with the fundamental concepts of
91  <a href="http://carbon.cudenver.edu/~hgreenbe/courseware/LPshort/intro.html" target="_top">
92  linear programming</a> (LP) and
93  <a href="http://carbon.cudenver.edu/~hgreenbe/courseware/MIP/intro.html" target="_top">
94  mixed integer programming</a> (MIP).
95  </p><p>
96
97CBC relies on other parts of the COIN repository. CBC needs a LP solver and relies on the COIN Open Solver Inteface (OSI) to communicate with the user's choice of solver. Any LP solver with an OSI interface can be used with CBC. The LP solver expected to be used most commonly is COIN's native linear program solver, CLP. For cut generators, CBC relies on the COIN Cut Generation Library (CGL). Any cut generator written to CGL standards can be used with CBC. Some of the cut generators in CGL rely on other parts of COIN, e.g., CGL's Gomory cut generator rely on the factorization functionality of <tt class="classname">CoinFactorization</tt>. This document assumes basic familiarity with OSI and CGL.
98</p><p>
99Technically speaking, CBC accesses the solver (and sometime the model and data it contains) through an <tt class="classname">OSISolverInterface</tt>. For the sake of simplicity, we will refer to the <tt class="classname">OsiSolverInterface</tt> as "the solver" in this document, rather than "the standard application programming interface to the solver." We hope any confusion caused by blurring this distinction will be mitigated by the shorter sentences. 
100 
101</p><p>
102In summary, readers should have the following prerequisites:
103   </p><div class="itemizedlist"><ul type="disc"><li>C++ knowledge,</li><li>LP and MIP fundamentals, and </li><li>OSI familiarity.</li></ul></div><p>
104</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3342019"></a>Preliminaries</h2></div></div><div></div></div><p>
105  </p><div class="itemizedlist"><ul type="disc"><li>Unless otherwise stated, the problem being optimized is a minimization problem. </li><li>The terms "model" and "problem" are used synonymously.</li><li>Notation: We use the convention of appending an underscore to
106              a variable in order to distinguish member data of a class.</li><li>The Cbc Samples directory, <tt class="filename">COIN/Cbc/Samples</tt> 
107              contains the source code for the examples in the Guide.</li><li>The sample code in the Guide is written for illustrative
108              purposes of the CBC concepts and usage. The sample code is not
109              necessarily written for performance.</li></ul></div><p>
110</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3413036"></a>
111Branch-and-Cut Overview
112</h2></div></div><div></div></div><p>
113  Before examining CBC in more detail, we tersely describe the basic branch-and-cut algorithm by way of example, (which should really be called branch-and-cut-and-bound) and show the major C++ class(es) in CBC related to each step. The major CBC classes, labeled (A) through (F), are described in <a href="#assClasses" title="Table 1.1. Associated Classes">Table 1.1</a>.
114 </p><p>
115Step 1. (Bound) Given a MIP model to minimize where some variables must take on integer values (e.g., 0, 1, or 2), relax the integrality requirements (e.g., consider each "integer" variable to be continuous with a lower bound of 0.0 and an upper bound of 2.0). Solve the resulting linear model with an LP solver to obtain a lower bound on the MIP's objective function value.  If the optimal LP solution has integer values for the MIP's integer variables, we are finished. Any MIP-feasible solution provides an upper bound on the objective value. The upper bound equals the lower bound; the solution is optimal.   
116 </p><p> 
117Step 2. (Branch) Otherwise, there exists an "integer" variable with a non-integral value. Choose one non-integral variable (e.g., with value 1.3) (A)(B) and branch. Create two
118<sup>[<a id="id3413203" href="#ftn.id3413203">2</a>]</sup>
119nodes, one with the branching variable having an upper bound of 1.0, and the other with the branching variable having a lower bound of 2.0. Add the two nodes to the search tree.
120 </p><p>
121While (search tree is not empty) {
122</p><p> 
123   Step 3. (Choose Node) Pick a node off the tree (C)(D)
124</p><p>
125   Step 4. (Re-optimize LP) Create an LP relaxation and solve.
126</p><p>
127   Step 5. (Bound) Interrogate the optimal LP solution, and try to prune the node by one of the following.
128   </p><div class="itemizedlist"><ul type="disc"><li>
129    LP is infeasible, prune the node.
130    </li><li>
131    Else, the optimal LP solution value of the node exceeds the current upper bound, prune the node. 
132    </li><li>
133    Else, the optimal LP solution of the node does not exceed the current upper bound and the solution is feasible to the MIP. Update the upper bound, and the best known MIP solution, and  prune the node by optimality.         
134    </li></ul></div><p> 
135</p><p>
136   Step 6. (Branch) If we were unable to prune the node, then branch. Choose one non-integral variable to branch on (A)(B). Create two nodes and add them to the search tree.
137}
138 </p><p>     
139This is the outline of a "branch-and-bound" algorithm. If in optimizing the linear programs, we use cuts to tighten the LP relaxations (E)(F), then we have a "branch-and-cut" algorithm. (Note, if cuts are only used in Step 1, the method is called a "cut-and-branch" algorithm.)
140 
141  </p><div class="table"><a id="assClasses"></a><p class="title"><b>Table 1.1. Associated Classes</b></p><table summary="Associated Classes" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th>
142    Note
143    </th><th>
144    Class name
145    </th><th>
146    Description
147    </th></tr></thead><tbody><tr><td align="left" valign="top">
148      (A)
149      </td><td align="left" valign="top"><tt class="classname">CbcBranch...</tt></td><td align="left" valign="top">
150      These classes define the nature of MIP's discontinuity.  The simplest discontinuity
151      is a variable which must take an integral value. Other types of discontinuities
152      exist, e.g., lot-sizing variables.
153      </td></tr><tr><td align="left" valign="top">
154      (B)
155      </td><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top">
156      This class decides which variable/entity to branch on next.
157      Even advanced users will probably only interact with this class by setting
158      <tt class="classname">CbcModel</tt> parameters ( e.g., priorities).
159      </td></tr><tr><td align="left" valign="top">
160      (C)
161      </td><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top">
162      All unsolved models can be thought of as being nodes on a tree where each
163      node (model) can branch two or more times. The interface with this class is helpful to know, but
164the user can pretty safely ignore the inner workings of this class.
165      </td></tr><tr><td align="left" valign="top">
166      (D)
167      </td><td align="left" valign="top"><tt class="classname">CbcCompare...</tt></td><td align="left" valign="top">
168      These classes are used in determine which of the unexplored nodes in the tree to consider next. These
169      classes are very small simple classes that can be tailored to suit the problem.
170      </td></tr><tr><td align="left" valign="top">
171      (E)
172      </td><td align="left" valign="top"><tt class="classname">CglCutGenerators</tt></td><td align="left" valign="top">
173      Any cut generator from CGL can be used in CBC. The cut generators are passed to CBC with parameters
174      which modify when each generator will be tried. All cut generators should be tried to
175      determine which are effective. Few users will write their own cut generators.
176      </td></tr><tr><td align="left" valign="top">
177      (F)
178      </td><td align="left" valign="top"><tt class="classname">CbcHeuristics</tt></td><td align="left" valign="top">
179      Heuristics are very important for obtaining valid solutions quickly.  Some
180      heuristics are available, but this is an area where it is useful and interesting to
181      write specialized ones.
182      </td></tr></tbody></table></div><p>
183  There are a number of resources available to help new CBC users get started.
184  This document is designed to be used in conjunction with the files in the
185  Samples subdirectory of the main CBC directory (<tt class="filename">COIN/Cbc/Samples</tt>).
186  The Samples illustrate how to use CBC and may also serve as useful starting points
187  for user projects.  In the event that either this document or the available
188  <a href="#doxygen" title="Appendix B. Doxygen">Doxygen content</a> conflicts with the observed
189  behavior of the source code, the comments in the header files, found in
190  <tt class="filename">COIN/Cbc/include</tt>, are the ultimate reference.
191  </p></div><div class="footnotes"><br /><hr width="100" align="left" /><div class="footnote"><p><sup>[<a id="ftn.id3342326" href="#id3342326">1</a>] </sup>
192        The complete acronym is "COIN-OR" which stands for the Compuational Infrastructure for Operations Research. For simplicity (and in keeping with the directory and function names) we will simply use "COIN".
193        </p></div><div class="footnote"><p><sup>[<a id="ftn.id3413203" href="#id3413203">2</a>] </sup>
194The current implementation of CBC allow two branches to be created. More general number of branches could be implemented.
195</p></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="cbcmodelclass"></a>Chapter 2. 
196   The CBC Model Class
197  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#hierarchy">
198  Overview
199  </a></dt><dt><a href="#firstexample">
200  Simple Branch-and-Bound Example
201  </a></dt><dt><a href="#osiAndCbc">
202The Relationship Between OSI and CBC
203</a></dt><dt><a href="#gettingsolution">
204  Getting Solution Information
205  </a></dt><dt><a href="#setsandgets">
206   Useful Set and Get Methods in CbcModel
207  </a></dt><dt><a href="#majormethods">
208  Impacting the Solution Process
209  </a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="hierarchy"></a>
210  Overview
211  </h2></div></div><div></div></div><p>
212  The main class in CBC is <tt class="classname">CbcModel</tt>.  The <tt class="classname">CbcModel</tt> class is where most
213  of the parameter setting is done. The absolute minimum number of actions taken with <tt class="classname">CbcModel</tt> is two,
214    </p><div class="itemizedlist"><ul type="disc"><li>
215    <tt class="function">CbcModel(OsiSolverInterface &amp; linearSolver)</tt> as constructor, and
216    </li><li>
217    <tt class="function">branchAndBound()</tt> for solving the problem.   
218    </li></ul></div><p>
219  </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="firstexample"></a>
220  Simple Branch-and-Bound Example
221  </h2></div></div><div></div></div><p>
222  The first sample program shows how to perform simple branch-and-bound with CBC.  This program is short enough to present in full.  Most of the remaining examples will take the form of small code fragments.
223  The complete code for all the examples in this Guide can be found in the CBC Samples directory, <tt class="filename">COIN/Cbc/Samples</tt>.
224
225  </p><div class="example"><a id="minimum.cpp"></a><p class="title"><b>Example 2.1. minimum.cpp</b></p><pre class="programlisting">
226   
227// Copyright (C) 2005, International Business Machines
228// Corporation and others.  All Rights Reserved.
229
230#include "CbcModel.hpp"
231
232// Using CLP as the solver
233#include "OsiClpSolverInterface.hpp"
234
235int main (int argc, const char *argv[])
236{
237  OsiClpSolverInterface solver1;
238
239  // Read in example model in MPS file format
240  // and assert that it is a clean model
241  int numMpsReadErrors = solver1.readMps("../../Mps/Sample/p0033.mps","");
242  assert(numMpsReadErrors==0);
243
244  // Pass the solver with the problem to be solved to CbcModel
245  CbcModel model(solver1);
246
247  // Do complete search
248  model.branchAndBound();
249
250  /* Print the solution.  CbcModel clones the solver so we
251     need to get current copy from the CbcModel */
252  int numberColumns = model.solver()-&gt;getNumCols();
253   
254  const double * solution = model.bestSolution();
255   
256  for (int iColumn=0;iColumn&lt;numberColumns;iColumn++) {
257    double value=solution[iColumn];
258    if (fabs(value)&gt;1.0e-7&amp;&amp;model.solver()-&gt;isInteger(iColumn))
259      printf("%d has value %g\n",iColumn,value);
260   }
261  return 0;
262}   
263     
264  </pre></div><p>
265  The program in <a href="#minimum.cpp" title="Example 2.1. minimum.cpp">Example 2.1</a> creates a <tt class="classname">OsiClpSolverInterface</tt> solver interface (i.e., <tt class="varname">solver1</tt>), and reads an MPS file. If there are no errors, the program passes the problem to <tt class="classname">CbcModel</tt> which solves the problem using the branch-and-bound algorithm. The part of the program which solves the problem is very small (one line!) but before that one line, the LP solver (i.e., <tt class="varname">solver1</tt>) had to be created and populated with the problem. After that one line, the results were printed out.
266 </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="osiAndCbc"></a>
267The Relationship Between OSI and CBC
268</h2></div></div><div></div></div><p> 
269The program in <a href="#minimum.cpp" title="Example 2.1. minimum.cpp">Example 2.1</a> illustrates the dependency of CBC on 
270  the <tt class="classname">OsiSolverInterface</tt> class. The constructor of <tt class="classname">CbcModel</tt> takes a pointer to an <tt class="classname">OsiSolverInterface</tt> (i.e., a solver). The <tt class="classname">CbcModel</tt> clones the solver, and uses its own instance of the solver. The <tt class="classname">CbcModel</tt>'s solver and the original solver (e.g., <tt class="varname">solver1</tt>) are not in sync unless the user synchronizes them. The user can always access the <tt class="classname">CbcModel</tt>'s solver through the <tt class="function">model()</tt> class.  To synchronize the two solvers, explicitly refreshing the original, e.g., 
271 </p><pre class="programlisting">
272  solver1 = model.solver();
273</pre><p>
274<tt class="classname">CbcModel</tt>'s method <tt class="function">solver()</tt> returns a pointer to CBC's cloned solver.
275</p><p>
276For convenience, many of the OSI methods to access problem data have identical method names in  <tt class="classname">CbcModel</tt>. (It's just more convenient to type <tt class="function">model.getNumCols()</tt> rather than <tt class="function">model.solver()-&gt;getNumCols()</tt>). The <tt class="classname">CbcModel</tt> refreshes its solver at certain logical points during the algorithm. At these points, the information from the <tt class="classname">CbcModel</tt> <tt class="varname">model</tt> will match the information from the <tt class="function">model.solver()</tt>. Elsewhere, the information may vary. For instance, the method <tt class="function">CbcModel::bestSolution()</tt> will contain the best solution so far, the OSI method <tt class="function">getColSolution()</tt> may not. In this case, it is safer to use <tt class="function">CbcModel::bestSolution()</tt>.
277</p><p>
278While all the OSI methods used in <tt class="filename">minimum.cpp</tt> have equivalent methods in <tt class="classname">CbcModel</tt>, there are some OSI methods which do not. For example, if  the program produced a lot of undesired output, one might add the line
279</p><pre class="programlisting">
280  model.solver()-&gt;setHintParam(OsiDoReducePrint,true,OsiHintTry);
281</pre><p> 
282 
283  to reduce the output. There is no <tt class="function">setHintParam()</tt> method in <tt class="classname">CbcModel</tt>.
284  </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="gettingsolution"></a>
285  Getting Solution Information
286  </h2></div></div><div></div></div><p>
287  Optimality can be checked through a call to <tt class="function">model.isProvenOptimal()</tt>.  Also
288  available are <tt class="function">isProvenInfeasible()</tt>,
289  <tt class="function">isSolutionLimitReached()</tt>,
290  <tt class="function">isNodeLimitReached()</tt> or the feared
291  <tt class="function">isAbandoned()</tt>. There is also
292  <tt class="function">int status()</tt> which returns 0 if finished (which includes the case when the algorithm is finished because it has been proved infeasible), 1 if stopped by user, and 2 if difficulties arose.
293  </p><p>
294  In addition to these <tt class="classname">CbcModel</tt> methods, solution values can be accessed via OSI methods.  The OSI methods pick up the current solution in the <tt class="classname">CBCModel</tt>.  The current solution will match the best solution found so far if called after <tt class="function">branchAndBound()</tt> and a solution was found.
295  </p><div class="table"><a id="id3415008"></a><p class="title"><b>Table 2.1. 
296  Methods for Getting Solution Information from OSI
297  </b></p><table summary="&#10;  Methods for Getting Solution Information from OSI &#10;  " border="0"><colgroup><col /><col /></colgroup><thead><tr><th>
298      Purpose
299      </th><th>
300      Name
301      </th><th>
302      Notes
303      </th></tr></thead><tbody><tr><td align="left" valign="top">
304      Primal column solution
305      </td><td align="left" valign="top"><tt class="function">const double * getColSolution()</tt></td><td align="left" valign="top">
306      The OSI method will return the best solution found thus far, unless none has been found. It is safer to use <tt class="classname">CbcModel</tt> version, <tt class="function">CbcModel::bestSolution()</tt></td></tr><tr><td align="left" valign="top">
307      Dual row solution
308      </td><td align="left" valign="top"><tt class="function">const double * getRowPrice()</tt></td><td align="left" valign="top">
309      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowPrice()</tt>.
310      </td></tr><tr><td align="left" valign="top">
311      Primal row solution
312      </td><td align="left" valign="top"><tt class="function">const double * getRowActivity()</tt></td><td align="left" valign="top">
313      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowActivity()</tt>.
314      </td></tr><tr><td align="left" valign="top">
315      Dual column solution
316      </td><td align="left" valign="top"><tt class="function">const double * getReducedCost()</tt></td><td align="left" valign="top">
317      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::gtReducedCost()</tt>.
318      </td></tr><tr><td align="left" valign="top">
319      Number of rows in model
320      </td><td align="left" valign="top"><tt class="function">int getNumRows()</tt></td><td align="left" valign="top">
321      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumRows()</tt>. Note: the number of rows can change due to cuts.
322      </td></tr><tr><td align="left" valign="top">
323      Number of columns in model
324      </td><td align="left" valign="top"><tt class="function">int getNumCols()</tt></td><td align="left" valign="top">
325      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumCols()</tt>.
326      </td></tr></tbody></table></div></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="setsandgets"></a>
327   Useful Set and Get Methods in <tt class="classname">CbcModel</tt>
328  </h2></div></div><div></div></div><p>
329Most of the parameter setting in CBC is done through <tt class="classname">CbcModel</tt> methods. The most commonly used set and get methods are listed in <a href="#setGet" title="Table 2.2. Useful Set and Get Methods in CbcModel">Table 2.2</a>.
330</p><div class="table"><a id="setGet"></a><p class="title"><b>Table 2.2. Useful Set and Get Methods in <tt class="classname">CbcModel</tt></b></p><table summary="Useful Set and Get Methods in CbcModel" border="0"><colgroup><col /><col /></colgroup><thead><tr><th>
331    Method(s)
332    </th><th>
333    Description
334    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="function">bool setMaximumNodes(int value)</tt><br /><tt class="function">int getMaximumNodes() const</tt><br /><tt class="function">bool setMaximumSeconds(double value)</tt><br /><tt class="function">double getMaximumSeconds()</tt><br /><tt class="function">bool setMaximumSolutions(double value)</tt><br /><tt class="function">double getMaximumSolutions() const</tt></td><td align="left" valign="top">
335      These set methods tell CBC to stop after a given number of nodes,
336      seconds, or solutions is reached. The get methods return the corresponding values.
337      </td></tr><tr><td align="left" valign="top"><tt class="function">bool setIntegerTolerance(double value) const</tt><br /><tt class="function">double getIntegerTolerance() const</tt></td><td align="left" valign="top">
338      An integer variable is deemed to be at an integral value if it is no further than this <i class="parameter"><tt>value</tt></i> (tolerance) away.
339      </td></tr><tr><td align="left" valign="top"><tt class="function">bool setAllowableGap(double value)</tt><br /><tt class="function">double getAllowableGap() const</tt><br /><tt class="function">bool setAllowablePercentageGap(double value)</tt><br /><tt class="function">double getAllowablePercentageGap() const</tt><br /><tt class="function">bool setAllowableFractionGap(double value)</tt><br /><tt class="function">double getAllowableFractionGap() const</tt><br /></td><td align="left" valign="top"><tt class="classname">CbcModel</tt> returns if the gap between the best known solution and the best
340      possible solution is less than this <i class="parameter"><tt>value</tt></i>, or as a percentage, or a fraction.
341      </td></tr><tr><td align="left" valign="top"><tt class="function">void setNumberStrong(double value) </tt><br /><tt class="function">int numberStrong()
342<sup>[<a id="id3415743" href="#ftn.id3415743">a</a>]</sup> const </tt></td><td align="left" valign="top">
343      These methods set or get the maximum number of candidates at a node to
344      be evaluated for strong branching.
345      </td></tr><tr><td align="left" valign="top"><tt class="function">void setPrintFrequency(int value) </tt><br /><tt class="function">int printFrequency() const</tt></td><td align="left" valign="top">
346      Controls the number of nodes evaluated between status prints.
347      Print frequency has a very slight overhead, if <i class="parameter"><tt>value</tt></i> is small.
348      </td></tr><tr><td align="left" valign="top"><tt class="function">int getNodeCount() const</tt></td><td align="left" valign="top">
349      Returns number of nodes evaluated in the search.
350      </td></tr><tr><td align="left" valign="top"><tt class="function">int numberRowsAtContinuous() const</tt></td><td align="left" valign="top">
351      Returns number of rows in the problem when handed to the solver (i.e., before cuts where added). Commonly used in implementing heuristics.
352      </td></tr><tr><td align="left" valign="top"><tt class="function">int  numberIntegers() const</tt><br /><tt class="function">const int * integerVariable() const</tt></td><td align="left" valign="top">
353      Returns number of integer variables and an array specifying them.
354      </td></tr><tr><td align="left" valign="top"><tt class="function">bool isBinary(int colIndex) const</tt><br /><tt class="function">bool isContinuous(int colIndex) const</tt><br /><tt class="function">bool isInteger(int colIndex) const</tt></td><td align="left" valign="top">
355      Returns information on variable <i class="parameter"><tt>colIndex</tt></i>. OSI methods
356      can be used to set these attributes (before handing the model to <tt class="classname">CbcModel</tt>).
357      </td></tr><tr><td align="left" valign="top"><tt class="function">double getObjValue() const</tt></td><td align="left" valign="top">
358      This method returns the best objective value so far.
359      </td></tr><tr><td align="left" valign="top"><tt class="function">double getCurrentObjValue() const</tt></td><td align="left" valign="top">
360      This method returns the current objective value.
361      </td></tr><tr><td align="left" valign="top"><tt class="function">const double * getObjCoefficients() const</tt><br /></td><td align="left" valign="top">
362      This method return the objective coefficients.
363      </td></tr><tr><td align="left" valign="top"><tt class="function">const double * getRowLower() const</tt><br /><tt class="function">const double * getRowUpper() const</tt><br /><tt class="function">const double * getColLower() const</tt><br /><tt class="function">const double * getColUpper() const</tt><br /></td><td align="left" valign="top">
364      These methods return the lower and upper bounds on row and column activities.
365      </td></tr><tr><td align="left" valign="top"><tt class="function">const CoinPackedMatrix * getMatrixByRow() const</tt></td><td align="left" valign="top">
366      This method returns a pointer to a row copy of matrix stored as a
367      <tt class="classname">CoinPackedMatrix</tt> which can be further examined.
368      </td></tr><tr><td align="left" valign="top"><tt class="function">const CoinPackedMatrix * getMatrixByCol() const</tt></td><td align="left" valign="top">
369      This method returns a pointer to a column copy of matrix stored as a
370      <tt class="classname">CoinPackedMatrix</tt> which can be further examined.
371      </td></tr><tr><td align="left" valign="top"><tt class="function">CoinBigIndex getNumElements() const</tt><sup>[<a id="id3416296" href="#ftn.id3416296">b</a>]</sup></td><td align="left" valign="top">
372      Returns the number of nonzero elements in the problem matrix.
373      </td></tr><tr><td align="left" valign="top"><tt class="function">void setObjSense(double value)</tt><br /><tt class="function">double getObjSense() const</tt></td><td align="left" valign="top">
374      These methods set and get the objective sense.  The parameter
375      <i class="parameter"><tt>value</tt></i> should be +1 to minimize and -1 to maximize.
376      </td></tr></tbody><tbody class="footnotes"><tr><td colspan="2"><div class="footnote"><p><sup>[<a id="ftn.id3415743" href="#id3415743">a</a>] </sup>
377This methods (and some of the other) do not follow the "get" convention. The convention has changed over time and there are still some inconsistencies to be cleaned up.
378</p></div><div class="footnote"><p><sup>[<a id="ftn.id3416296" href="#id3416296">b</a>] </sup> 
379        <span class="type">CoinBigIndex</span> is a <tt class="function">typedef</tt> which in
380        most cases is the same as <span class="type">int</span>.
381        </p></div></td></tr></tbody></table></div></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="majormethods"></a>
382  Impacting the Solution Process
383  </h2></div></div><div></div></div><p>
384<tt class="classname">CbcModel</tt> is extremely flexible and customizable. The class structure of CBC is designed to make the most commonly desired customizations of branch-and-cut possible. These include:
385    </p><div class="itemizedlist"><ul type="disc"><li>
386     selecting the next node to consider in the search tree,
387    </li><li>
388    determining which variable to branch on,
389    </li><li>
390    using heuristics to generate MIP-feasible solutions quickly,
391    </li><li>
392    including cut generation when solving the LP-relaxations, and
393    </li><li>
394    invoking customized subproblem solvers.
395    </li></ul></div><p>
396
397
398To enable this flexibility,  <tt class="classname">CbcModel</tt> uses other classes in CBC (some of which are virtual and may have multiple instances). Not all classes are created equal. The two tables below list in alphabetical order the classes used by <tt class="classname">CbcModel</tt> that are of most interest and of least interest.
399</p><div class="table"><a id="id3416491"></a><p class="title"><b>Table 2.3. Classes Used by CbcModel - Most Useful</b></p><table summary="Classes Used by CbcModel - Most Useful" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th>
400    Class name
401    </th><th>
402    Description
403    </th><th>
404    Notes
405    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareBase</tt></td><td align="left" valign="top">
406      Controls which node on the tree is selected.
407      </td><td align="left" valign="top">
408      The default is <tt class="classname">CbcCompareDefault</tt>. Other comparison classes in <tt class="filename">CbcCompareActual.hpp</tt> include <tt class="classname">CbcCompareDepth</tt> and <tt class="classname">CbcCompareObjective</tt>. Experimenting with these classes and creating new compare classes is easy.
409      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCutGenerator</tt></td><td align="left" valign="top">
410      A wrapper for <tt class="classname">CglCutGenerator</tt> with additional data to control when the cut generator is invoked during the tree search.
411      </td><td align="left" valign="top">
412      Other than knowing how to add a cut generator to <tt class="classname">CbcModel</tt>, there is not much the average user needs to know about this class. However, sophisticated users can implement their own cut generators. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcHeuristic</tt></td><td align="left" valign="top">
413      Heuristic that attempts to generate valid MIP-solutions leading to good upper bounds.
414      </td><td align="left" valign="top">
415      Specialized heuristics can dramatically improve branch-and-cut performance. As many different heuristics as desired can be used in CBC. Advanced users should consider implementing custom heuristics when tackling difficult problems. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcObject</tt></td><td align="left" valign="top">
416      Defines what it means for a variable to be satisfied. Used in branching.
417      </td><td align="left" valign="top">
418      Virtual class. CBC's concept of branching is based on the idea of an "object". An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparison of the effect of branching. Instances of objects include <tt class="classname">CbcSimpleInteger</tt>, <tt class="classname">CbcSimpleIntegerPseudoCosts</tt>, <tt class="classname">CbcClique</tt>, <tt class="classname">CbcSOS</tt> (type 1 and 2), <tt class="classname">CbcFollowOn</tt>, and <tt class="classname">CbcLotsize</tt>.
419      </td></tr><tr><td align="left" valign="top"><tt class="classname">OsiSolverInterface</tt></td><td align="left" valign="top">
420      Defines the LP solver being used and the LP model. Normally
421      a pointer to the desired <tt class="classname">OsiSolverInteface</tt> is passed to <tt class="classname">CbcModel</tt> before branch and cut.
422      </td><td align="left" valign="top">
423      Virtual class. The user instantiates the solver interface of their choice, e.g.,
424      <tt class="classname">OsiClpSolverInterface</tt>.
425      </td></tr></tbody></table></div><p>
426There is not much about the classes listed in <a href="#least" title="Table 2.4. Classes Used by CbcModel - Least Useful">Table 2.4</a> that the average user needs to know about.
427</p><div class="table"><a id="least"></a><p class="title"><b>Table 2.4. Classes Used by CbcModel - Least Useful</b></p><table summary="Classes Used by CbcModel - Least Useful" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th>
428    Class name
429    </th><th>
430    Description
431    </th><th>
432    Notes
433    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcBranchDecision</tt></td><td align="left" valign="top">
434      Used in choosing which variable to branch on, however, most of
435      the work is done by the definitions in <tt class="classname">CbcObject</tt>.
436      </td><td align="left" valign="top">
437      Defaults to <tt class="classname">CbcBranchDefaultDecision</tt>.
438      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCountRowCut</tt></td><td align="left" valign="top">
439      Interface to <tt class="classname">OsiRowCut</tt>. It counts the usage so cuts can gracefully vanish.
440      </td><td align="left" valign="top">
441      See <tt class="classname">OsiRowCut</tt> for more details. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top">
442      Controls which variable/entity is selected to be branch on.
443      </td><td align="left" valign="top">
444      Controlled via <tt class="classname">CbcModel</tt> parameters. Information from <tt class="classname">CbcNode</tt> can be useful in creating customized node selection rules.  </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcNodeInfo</tt></td><td align="left" valign="top">
445      Contains data on bounds, basis, etc. for one node of the search tree.
446      </td><td align="left" valign="top">
447      Header is located in <tt class="filename">CbcNode.hpp</tt>. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top">
448      Defines how the search tree is stored.
449      </td><td align="left" valign="top">
450      This class can be changed but it is not likely to be modified.</td></tr><tr><td align="left" valign="top"><tt class="classname">CoinMessageHandler</tt></td><td align="left" valign="top">
451      Deals with message handling
452      </td><td align="left" valign="top">
453      The user can inherit from <tt class="classname">CoinMessageHandler</tt> to specialize message handling. 
454      </td></tr><tr><td align="left" valign="top"><tt class="classname">CoinWarmStartBasis</tt></td><td align="left" valign="top">
455      Basis representation to be used by solver
456      </td><td align="left" valign="top"></td></tr></tbody></table></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="otherclasses"></a>Chapter 3. 
457  Selecting the Next Node in the Search Tree
458  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#comparison">CbcCompare - Comparison Methods</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="comparison"></a>CbcCompare - Comparison Methods</h2></div></div><div></div></div><p>
459  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
460</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>
461CBC 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="#compareTable" title="Table 3.1. Compare Classes Provided">Table 3.1</a>.
462  </p><div class="table"><a id="compareTable"></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>
463    Class name
464    </th><th>
465    Description
466    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareDepth</tt></td><td align="left" valign="top">
467      This will always choose the node deepest in tree.  It gives minimum
468      tree size but may take a long time to find the best solution.
469      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareObjective</tt></td><td align="left" valign="top">
470      This will always choose the node with the best objective value.  This may
471      give a very large tree.  It is likely that the first solution found
472      will be the best and the search should finish soon after the first solution
473      is found.
474      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareDefault</tt></td><td align="left" valign="top">
475      This is designed to do a mostly depth-first search until a solution has
476      been found. It then use estimates that are designed to give a slightly better solution.
477      If a reasonable number of nodes have been explored (or a reasonable number of
478      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.
479      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareEstimate</tt></td><td align="left" valign="top">
480      When pseudo costs are invoked, CBC uses the psuedo costs to guess a solution.  This class uses the guessed solution.
481      </td></tr></tbody></table></div><p>
482  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="#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="#nodeTable" title="Table 3.2. Information Available from CbcNode">Table 3.2</a> lists some commonly used methods to access information at a node.
483  </p><div class="table"><a id="nodeTable"></a><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">
484      Value of objective at the node.
485      </td></tr><tr><td align="left" valign="top"><tt class="function">int numberUnsatisfied() const</tt></td><td align="left" valign="top">
486      Number of unsatisfied integers (assuming branching
487      object is an integer - otherwise it might be number of unsatisfied sets).
488      </td></tr><tr><td align="left" valign="top"><tt class="function">int depth() const</tt></td><td align="left" valign="top">
489       Depth of the node in the search tree.
490      </td></tr><tr><td align="left" valign="top"><tt class="function">double guessedObjectiveValue() const</tt></td><td align="left" valign="top"> 
491     Returns the guessed objective value, if the user was setting this (e.g., if using pseudo costs).
492      </td></tr><tr><td align="left" valign="top"><tt class="function">int way() const</tt></td><td align="left" valign="top">
493       The way which branching would next occur from this node
494       (for more advanced use).
495      </td></tr><tr><td align="left" valign="top"><tt class="function">int variable() const</tt></td><td align="left" valign="top">
496       The branching "variable" (associated with the <tt class="classname">CbcBranchingObject</tt> -- for more advanced use).
497      </td></tr></tbody></table></div><p>
498</p><p>
499The 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
500  <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
501  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.
502</p><p>
503</p><div class="itemizedlist"><ul type="disc"><li><p>
5041) The number of solutions found so far
505  </p></li><li><p>
5062) The size of the tree (defined to be the number of active nodes)
507  </p></li><li><p>
5083) A weight, <tt class="varname">weight_</tt>, which is initialized to -1.0
509  </p></li><li><p>
5104) A saved value of weight, <tt class="varname">saveWeight_</tt> (for when weight is set back to -1.0 for special reason)
511  </p></li></ul></div><p>
512</p><p>
513Initially, <tt class="varname">weight</tt>_ is -1.0 and the search is biased towards depth first.  In
514fact, <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="#test" title="Example 3.1. CbcCompareUser::test()">Example 3.1</a>.
515</p><div class="example"><a id="test"></a><p class="title"><b>Example 3.1. <tt class="function">CbcCompareUser::test()</tt></b></p><pre class="programlisting">
516   
517// Returns true if y better than x
518bool
519CbcCompareUser::test (CbcNode * x, CbcNode * y)
520{
521  if (weight_==-1.0) {
522    // before solution
523    if (x-&gt;numberUnsatisfied() &gt; y-&gt;numberUnsatisfied())
524      return true;
525    else if (x-&gt;numberUnsatisfied() &lt; y-&gt;numberUnsatisfied())
526      return false;
527    else
528      return x-&gt;depth() &lt; y-&gt;depth();
529  } else {
530    // after solution.
531    // note: if weight_=0, comparison is based
532    //       solely on objective value
533    double weight = CoinMax(weight_,0.0);
534    return x-&gt;objectiveValue()+ weight*x-&gt;numberUnsatisfied() &gt; 
535      y-&gt;objectiveValue() + weight*y-&gt;numberUnsatisfied();
536  }
537}
538     
539  </pre></div><p>
540CBC 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="#newSolution" title="Example 3.2. CbcCompareUser::newSolution()">Example 3.2</a>.
541</p><div class="example"><a id="newSolution"></a><p class="title"><b>Example 3.2. <tt class="function">CbcCompareUser::newSolution()</tt></b></p><pre class="programlisting">
542   
543// This allows the test() method to change behavior by resetting weight_.
544// It is called after each new solution is found.
545void
546CbcCompareUser::newSolution(CbcModel * model,
547                               double objectiveAtContinuous,
548                               int numberInfeasibilitiesAtContinuous)
549{
550  if (model-&gt;getSolutionCount()==model-&gt;getNumberHeuristicSolutions())
551    return; // The number of solutions found by any means equals the
552            // number of solutions, so this solution was found by rounding.
553            // Ignore it.
554
555  // set weight_ to get close to this solution
556  double costPerInteger =
557    (model-&gt;getObjValue()-objectiveAtContinuous)/
558    ((double) numberInfeasibilitiesAtContinuous);
559  weight_ = 0.98*costPerInteger; // this aims for a solution
560                                 // slightly better than known.
561                                 // why 0.98? why not?! Experiment yourself.                                 
562  saveWeight_=weight_; // We're going to switching between depth-first and breadth-first
563                       // branching strategies, depending on what we find in the tree.
564                       // When doing depth first, we'll want to retrieve this weight.
565                       // So, let's save it.
566  numberSolutions_++;
567  if (numberSolutions_&gt;5)
568    weight_ =0.0; // comparison in test() will be
569                  // based strictly on objective value.
570}
571     
572  </pre></div><p>
573
574As 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="#everyK" title="Example 3.3. CbcCompareUser::every1000Nodes()">Example 3.3</a>.
575  </p><div class="example"><a id="everyK"></a><p class="title"><b>Example 3.3. <tt class="function">CbcCompareUser::every1000Nodes()</tt></b></p><pre class="programlisting">
576   
577// This allows the test() method to change behavior every 1000 nodes.
578bool
579CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
580{
581  if (numberNodes&gt;10000)
582    weight_ =0.0; // compare nodes based on objective value
583    // get size of tree
584  treeSize_ = model-&gt;tree()-&gt;size();
585  if (treeSize_&gt;10000) {
586    // set weight to reduce size most of time
587    if (treeSize_&gt;20000)
588      weight_=-1.0;
589    else if ((numberNodes%4000)!=0)  // Flip-flop between the strategies.
590                                     // Why 4000? Why not? Experiment yourself.
591      weight_=-1.0;
592    else
593      weight_=saveWeight_;
594  }
595  return numberNodes==11000; // resort if first time
596}
597     
598  </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="hueristicChap"></a>Chapter 4. 
599  Getting Good Bounds in CBC
600  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#heuristics">CbcHeuristic - Heuristic Methods</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="heuristics"></a>CbcHeuristic - Heuristic Methods</h2></div></div><div></div></div><p>
601  In practice, it is very useful to get a good solution reasonably fast. Any MIP-feasible solution produces an upper bound, and a good bound will greatly reduce the run time. Good solutions can satisfy the user
602  on very large problems where a complete search is impossible.  Obviously, heuristics are
603  problem dependent, although some do have more general use.
604  At present there is only one heuristic in CBC itself, <tt class="classname">CbcRounding</tt>. Hopefully, the number will grow. Other heuristics are in the <tt class="filename">COIN/Cbc/Samples</tt>
605  directory.  A heuristic tries to obtain a solution to the original
606  problem so it only needs to consider the original rows and does not have to use the
607  current bounds. CBC provides an abstract base class <tt class="classname">CbcHeuristic</tt> and a rounding heuristic in CBC.
608  </p><p>
609  This chapter describes how to build a greedy heuristic for a set covering problem, e.g., the miplib problem fast0507. A more general (and efficient) version of the heuristic is in <tt class="filename">CbcHeuristicGreedy.hpp</tt> and <tt class="filename">CbcHeuristicGreedy.cpp</tt> located in the <tt class="filename">COIN/Cbc/Samples</tt> directory, see <a href="#moreexamples" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
610More Samples
611</i></a>.
612</p><p>
613  The greedy heuristic will leave all variables taking value one at this node of the
614  tree at value one, and will initially set all other variables to value zero. 
615  All variables are then sorted in order of their cost
616  divided by the number of entries in rows which are not yet covered. (We may randomize that
617  value a bit so that ties will be broken in different ways on different runs of the heuristic.)
618  The best one is choosen, and set to one. The process is repeated. Because this is
619  a set covering problem (i.e., all constraints are ≥), the heuristic is guaranteed to find a solution (but not necessarily an improved solution). The speed of the heuristic could be improved by just redoing those affected, but for illustrative purposes we will keep it simple. (The speed could also be improved if all elements are 1.0).
620</p><p>
621  The key <tt class="classname">CbcHeuristic</tt> method is <tt class="function">int solution(double &amp; solutionValue,
622                                              double * betterSolution)</tt>.
623  The <tt class="function">solution()</tt> method returns 0 if no solution found, and returns 1 if a solution is found, in which case it fills in the objective value and primal solution.  The code in <tt class="filename">CbcHeuristicGreedy.cpp</tt> is a little more complicated than this following example. For instance, the code here assumes all variables are integer.  The important bit of data is a copy of the matrix (stored by column) before any cuts have been made.  The data used are bounds, objective and the matrix plus two work arrays.
624  </p><div class="example"><a id="id3421313"></a><p class="title"><b>Example 4.1. Data</b></p><pre class="programlisting">
625   
626  OsiSolverInterface * solver = model_-&gt;solver(); // Get solver from CbcModel
627  const double * columnLower = solver-&gt;getColLower(); // Column Bounds
628  const double * columnUpper = solver-&gt;getColUpper();
629  const double * rowLower = solver-&gt;getRowLower(); // We know we only need lower bounds
630  const double * solution = solver-&gt;getColSolution();
631  const double * objective = solver-&gt;getObjCoefficients(); // In code we also use min/max
632  double integerTolerance = model_-&gt;getDblParam(CbcModel::CbcIntegerTolerance);
633  double primalTolerance;
634  solver-&gt;getDblParam(OsiPrimalTolerance,primalTolerance);
635  int numberRows = originalNumberRows_; // This is number of rows when matrix was passed in
636  // Column copy of matrix (before cuts)
637  const double * element = matrix_.getElements();
638  const int * row = matrix_.getIndices();
639  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
640  const int * columnLength = matrix_.getVectorLengths();
641
642  // Get solution array for heuristic solution
643  int numberColumns = solver-&gt;getNumCols();
644  double * newSolution = new double [numberColumns];
645  // And to sum row activities
646  double * rowActivity = new double[numberRows];
647     
648  </pre></div><p>
649The <tt class="varname">newSolution</tt> is then initialized to the rounded down solution.
650</p><div class="example"><a id="id3421342"></a><p class="title"><b>Example 4.2. Initialize <tt class="varname">newSolution</tt></b></p><pre class="programlisting">
651   
652  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
653    CoinBigIndex j;
654    double value = solution[iColumn];
655    // Round down integer
656    if (fabs(floor(value+0.5)-value)&lt;integerTolerance)
657      value=floor(CoinMax(value+1.0e-3,columnLower[iColumn]));
658    // make sure clean
659    value = CoinMin(value,columnUpper[iColumn]);
660    value = CoinMax(value,columnLower[iColumn]);
661    newSolution[iColumn]=value;
662    if (value) {
663      double cost = objective[iColumn];
664      newSolutionValue += value*cost;
665      for (j=columnStart[iColumn];
666           j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
667        int iRow=row[j];
668        rowActivity[iRow] += value*element[j];
669      }
670    }
671  }
672     
673  </pre></div><p>
674
675
676At this point some row activities are below their lower bound. To correct the infeasibility, the variable which is cheapest in reducing the sum of infeasibilities is found and updated, and the process repeats.  This is a finite process. (The implementation could be faster, but is kept simple for illustrative purposes.)
677  </p><div class="example"><a id="id3421423"></a><p class="title"><b>Example 4.3. Create Feasible <tt class="varname">newSolution</tt> from Initial <tt class="varname">newSolution</tt></b></p><pre class="programlisting">
678   
679  while (true) {
680    // Get column with best ratio
681    int bestColumn=-1;
682    double bestRatio=COIN_DBL_MAX;
683    for (int iColumn=0;iColumn&lt;numberColumns;iColumn++) {
684      CoinBigIndex j;
685      double value = newSolution[iColumn];
686      double cost = direction * objective[iColumn];
687      // we could use original upper rather than current
688      if (value+0.99&lt;columnUpper[iColumn]) {
689        double sum=0.0; // Compute how much we will reduce infeasibility by
690        for (j=columnStart[iColumn];
691             j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
692          int iRow=row[j];
693          double gap = rowLower[iRow]-rowActivity[iRow];
694          if (gap&gt;1.0e-7) {
695            sum += CoinMin(element[j],gap);
696          if (element[j]+rowActivity[iRow]&lt;rowLower[iRow]+1.0e-7) {
697            sum += element[j];
698          }
699        }
700        if (sum&gt;0.0) {
701          double ratio = (cost/sum)*(1.0+0.1*CoinDrand48());
702          if (ratio&lt;bestRatio) {
703            bestRatio=ratio;
704            bestColumn=iColumn;
705          }
706        }
707      }
708    }
709    if (bestColumn&lt;0)
710      break; // we have finished
711    // Increase chosen column
712    newSolution[bestColumn] += 1.0;
713    double cost = direction * objective[bestColumn];
714    newSolutionValue += cost;
715    for (CoinBigIndex j=columnStart[bestColumn];
716         j&lt;columnStart[bestColumn]+columnLength[bestColumn];j++) {
717      int iRow = row[j];
718      rowActivity[iRow] += element[j];
719    }
720  }
721     
722  </pre></div><p>
723A solution value of <tt class="varname">newSolution</tt> is compared to the best solution value. If <tt class="varname">newSolution</tt> is an improvement, its feasibility is validated. We expect <tt class="varname">newSolution</tt> to be feasible, and are trapping for unexpected numerical errors.
724  </p><div class="example"><a id="id3421467"></a><p class="title"><b>Example 4.4. Check Solution Quality of <tt class="varname">newSolution</tt></b></p><pre class="programlisting">
725   
726  returnCode=0; // 0 means no good solution
727  if (newSolutionValue&lt;solutionValue) { // minimization
728    // check feasible
729    memset(rowActivity,0,numberRows*sizeof(double));
730    for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
731      CoinBigIndex j;
732      double value = newSolution[iColumn];
733      if (value) {
734        for (j=columnStart[iColumn];
735             j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
736          int iRow=row[j];
737          rowActivity[iRow] += value*element[j];
738        }
739      }
740    }
741    // check was approximately feasible
742    bool feasible=true;
743    for (iRow=0;iRow&lt;numberRows;iRow++) {
744      if(rowActivity[iRow]&lt;rowLower[iRow]) {
745        if (rowActivity[iRow]&lt;rowLower[iRow]-10.0*primalTolerance)
746          feasible = false;
747      }
748    }
749    if (feasible) {
750      // new solution
751      memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
752      solutionValue = newSolutionValue;
753      // We have good solution
754      returnCode=1;
755    }
756  }
757     
758  </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="branchChapter"></a>Chapter 5. 
759  Branching
760 </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#branchingIntro">Branching Overview</a></dt><dt><a href="#branching">Pseudo Cost Branching</a></dt><dt><a href="#followOn">Follow-On Branching</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="branchingIntro"></a>Branching Overview</h2></div></div><div></div></div><p>
761CBC's concept of branching is based on the idea of an "object". An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparsion of the effect of branching. Instances of objects include.
762</p><div class="itemizedlist"><ul type="disc"><li><tt class="classname">CbcSimpleInteger</tt>, </li><li><tt class="classname">CbcSimpleIntegerPseudoCosts</tt>,  </li><li><tt class="classname">CbcClique</tt>, </li><li><tt class="classname">CbcSOS</tt> (type 1 and 2), </li><li><tt class="classname">CbcFollowOn</tt>, and </li><li><tt class="classname">CbcLotsize</tt>.</li></ul></div><p>
763In <a href="#branchChapter" title="Chapter 5. &#10;  Branching&#10; ">Chapter 5, <i>
764  Branching
765 </i></a>, we give examples of how to use existing branching objects. (The next revision of this Guide should include an example of how to write your own branching object; Contributions of examples are welcome.)
766</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="branching"></a>Pseudo Cost Branching</h2></div></div><div></div></div><p>
767
768If the user declares variables as integer but does no more, then CBC will treat them
769as simple integer variables.  In many cases the user would like to do some more fine tuning. This section shows how to create integer variables with pseudo costs.  When pseudo costs are given then
770it is assumed that if a variable is at 1.3 then the cost of branching that variable down will be 0.3 times the down pseudo cost and the cost of branching up would be 0.7 times the up pseudo cost.  Pseudo costs can be used both for branching and for choosing a node.
771   The full code is in <tt class="filename">longthin.cpp</tt> located in the CBC Samples directory, see
772  <a href="#moreexamples" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
773More Samples
774</i></a>.
775</p><p> 
776  The idea is simple for set covering problems.
777  Branching up gets us much closer to an integer solution so we will encourage that direction by branch up if variable value &gt; 0.333333.
778  The expected cost of going up obviously depends on the cost of the
779  variable. The pseudo costs are choosen to reflect that fact.
780
781  </p><div class="example"><a id="pseudo"></a><p class="title"><b>Example 5.1. <tt class="classname">CbcSimpleIntegerPseudoCosts</tt></b></p><pre class="programlisting">
782   
783  int iColumn;
784  int numberColumns = solver3-&gt;getNumCols();
785  // do pseudo costs
786  CbcObject ** objects = new CbcObject * [numberColumns];
787  // Point to objective
788  const double * objective = model.getObjCoefficients();
789  int numberIntegers=0;
790  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
791    if (solver3-&gt;isInteger(iColumn)) {
792      double cost = objective[iColumn];
793      CbcSimpleIntegerPseudoCost * newObject =
794        new CbcSimpleIntegerPseudoCost(&amp;model,numberIntegers,iColumn,
795                                       2.0*cost,cost);
796      newObject-&gt;setMethod(3);
797      objects[numberIntegers++]= newObject;
798    }
799  }
800  // Now add in objects (they will replace simple integers)
801  model.addObjects(numberIntegers,objects);
802  for (iColumn=0;iColumn&lt;numberIntegers;iColumn++)
803    delete objects[iColumn];
804  delete [] objects;
805     
806  </pre></div><p>
807The code in <a href="#pseudo" title="Example 5.1. CbcSimpleIntegerPseudoCosts">Example 5.1</a> also tries to give more importance to variables with more
808coefficients.  Whether this sort of thing is worthwhile should be the subject of experimentation.
809
810
811</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="followOn"></a>Follow-On Branching</h2></div></div><div></div></div><p>
812In crew scheduling, the problems are long and thin. A problem may have a few rows but many thousands of variables.  Branching a variable to 1 is very powerful as it fixes many other variables to zero, but branching to zero is very weak as thousands of variables can increase from zero.  In crew scheduling problems, each constraint is a flight leg, e.g., JFK airport to DFW airport.
813From DFW there may be several flights the crew could take next - suppose one flight is
814the 9:30 flight from DFW to LAX airport.  A binary branch is that the crew arriving
815at DFW either take the 9:30 flight to LAX or they don't.  This "follow-on" branching does not
816fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW
817constraint into two groups - those with entries in the DFW-LAX constraint and those without
818entries.
819</p><p>
820   The full sample code for follow-on brancing is in <tt class="filename">crew.cpp</tt>
821  located in the CBC Samples directory, see
822  <a href="#moreexamples" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
823More Samples
824</i></a>).  In this case, the simple integer
825variables are left which may be necessary if other sorts of constraints exist. Follow-on branching rules are to be considered first, so the priorities are set to indicate the follow-on rules take precedence. Priority 1 is the highest priority.
826
827</p><div class="example"><a id="id3421836"></a><p class="title"><b>Example 5.2. <tt class="classname">CbcFollowOn</tt></b></p><pre class="programlisting">
828   
829  int iColumn;
830  int numberColumns = solver3-&gt;getNumCols();
831  /* We are going to add a single follow-on object but we
832     want to give low priority to existing integers
833     As the default priority is 1000 we don't actually need to give
834     integer priorities but it is here to show how.
835  */
836  // Normal integer priorities
837  int * priority = new int [numberColumns];
838  int numberIntegers=0;
839  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
840    if (solver3-&gt;isInteger(iColumn)) {
841      priority[numberIntegers++]= 100; // low priority
842    }
843  }
844  /* Second parameter is set to true for objects,
845     and false for integers. This indicates integers */
846  model.passInPriorities(priority,false);
847  delete [] priority;
848  /* Add in objects before we can give them a priority.
849     In this case just one object
850     - but it shows the general method
851  */
852  CbcObject ** objects = new CbcObject * [1];
853  objects[0]=new CbcFollowOn(&amp;model);
854  model.addObjects(1,objects);
855  delete objects[0];
856  delete [] objects;
857  // High priority
858  int followPriority=1;
859  model.passInPriorities(&amp;followPriority,true);
860     
861  </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="CutsChap"></a>Chapter 6. Cutting planes</h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#cuts">Using Cut Generators with CBC</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="cuts"></a>Using Cut Generators with CBC</h2></div></div><div></div></div><p>
862In the next version of this Guide, we need to have an example illustrating how to use COIN's CGL with CBC. Contribtions are welcome.
863
864  </p></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="SolverChap"></a>Chapter 7. 
865  Advanced Solver Uses
866</h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#solver">Creating a Solver via Inheritance</a></dt><dt><a href="#quadratic">Quadratic MIP</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="solver"></a>Creating a Solver via Inheritance</h2></div></div><div></div></div><p>
867  CBC uses a generic <tt class="classname">OsiSolverInterface</tt> and its <tt class="function">resolve</tt> capability.
868  This does not give much flexibility so advanced users can inherit from their interface
869  of choice.  This section illustrates how to implement a specialized solver for a long thin problem, e.g., fast0507 again.  As with the other examples in the Guide, the sample code is not guaranteed to be the fastest way to solve the problem. The main purpose of the example is to illustrate techniques. The full source is in <tt class="filename">CbcSolver2.hpp</tt> and <tt class="filename">CbcSolver2.cpp</tt> located in the CBC Samples directory, see
870  <a href="#moreexamples" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
871More Samples
872</i></a>.
873</p><p>
874The method <tt class="function">initialSolve</tt> is called a few times in CBC, and provides a convenient starting point. The <tt class="varname">modelPtr_</tt> derives from <tt class="classname">OsiClpSolverInterface</tt>.
875  </p><div class="example"><a id="initialSolve"></a><p class="title"><b>Example 7.1. <tt class="function">initialSolve()</tt></b></p><pre class="programlisting">
876   
877  // modelPtr_ is of type ClpSimplex *
878  modelPtr_-&gt;setLogLevel(1); // switch on a bit of printout
879  modelPtr_-&gt;scaling(0); // We don't want scaling for fast0507
880  setBasis(basis_,modelPtr_); // Put basis into ClpSimplex
881  // Do long thin by sprint
882  ClpSolve options;
883  options.setSolveType(ClpSolve::usePrimalorSprint);
884  options.setPresolveType(ClpSolve::presolveOff);
885  options.setSpecialOption(1,3,15); // Do 15 sprint iterations
886  modelPtr_-&gt;initialSolve(options); // solve problem
887  basis_ = getBasis(modelPtr_); // save basis
888  modelPtr_-&gt;setLogLevel(0); // switch off printout
889     
890  </pre></div><p>
891The <tt class="function">resolve()</tt> method is more complicated than <tt class="function">initialSolve()</tt>.  The main pieces of data are a counter <tt class="varname">count_</tt> which is incremented each solve and an integer array <tt class="varname">node_</tt> which stores the last time
892a variable was active in a solution.  For the first few solves, the normal Dual Simplex is called and
893<tt class="varname">node_</tt> array is updated.
894</p><div class="example"><a id="id3422104"></a><p class="title"><b>Example 7.2. First Few Solves</b></p><pre class="programlisting">
895   
896  if (count_&lt;10) {
897    OsiClpSolverInterface::resolve(); // Normal resolve
898    if (modelPtr_-&gt;status()==0) {
899      count_++; // feasible - save any nonzero or basic
900      const double * solution = modelPtr_-&gt;primalColumnSolution();
901      for (int i=0;i&lt;numberColumns;i++) {
902        if (solution[i]&gt;1.0e-6||modelPtr_-&gt;getStatus(i)==ClpSimplex::basic) {
903          node_[i]=CoinMax(count_,node_[i]);
904          howMany_[i]++;
905        }
906      }
907    } else {
908      printf("infeasible early on\n");
909    }
910  }
911     
912  </pre></div><p>
913After the first few solves, only those variables which took part in a solution in the last so many
914solves are used.  As fast0507 is a set covering problem, any rows which are already covered can be taken out.
915  </p><div class="example"><a id="id3422132"></a><p class="title"><b>Example 7.3. Create Small Sub-Problem</b></p><pre class="programlisting">
916   
917    int * whichRow = new int[numberRows]; // Array to say which rows used
918    int * whichColumn = new int [numberColumns]; // Array to say which columns used
919    int i;
920    const double * lower = modelPtr_-&gt;columnLower();
921    const double * upper = modelPtr_-&gt;columnUpper();
922    setBasis(basis_,modelPtr_); // Set basis
923    int nNewCol=0; // Number of columns in small model
924    // Column copy of matrix
925    const double * element = modelPtr_-&gt;matrix()-&gt;getElements();
926    const int * row = modelPtr_-&gt;matrix()-&gt;getIndices();
927    const CoinBigIndex * columnStart = modelPtr_-&gt;matrix()-&gt;getVectorStarts();
928    const int * columnLength = modelPtr_-&gt;matrix()-&gt;getVectorLengths();
929   
930    int * rowActivity = new int[numberRows]; // Number of columns with entries in each row
931    memset(rowActivity,0,numberRows*sizeof(int));
932    int * rowActivity2 = new int[numberRows]; // Lower bound on row activity for each row
933    memset(rowActivity2,0,numberRows*sizeof(int));
934    char * mark = (char *) modelPtr_-&gt;dualColumnSolution(); // Get some space to mark columns
935    memset(mark,0,numberColumns);
936    for (i=0;i&lt;numberColumns;i++) {
937      bool choose = (node_[i]&gt;count_-memory_&amp;&amp;node_[i]&gt;0); // Choose if used recently
938      // Take if used recently or active in some sense
939      if ((choose&amp;&amp;upper[i])
940          ||(modelPtr_-&gt;getStatus(i)!=ClpSimplex::atLowerBound&amp;&amp;
941             modelPtr_-&gt;getStatus(i)!=ClpSimplex::isFixed)
942          ||lower[i]&gt;0.0) {
943        mark[i]=1; // mark as used
944        whichColumn[nNewCol++]=i; // add to list
945        CoinBigIndex j;
946        double value = upper[i];
947        if (value) {
948          for (j=columnStart[i];
949               j&lt;columnStart[i]+columnLength[i];j++) {
950            int iRow=row[j];
951            assert (element[j]==1.0);
952            rowActivity[iRow] ++; // This variable can cover this row
953          }
954          if (lower[i]&gt;0.0) {
955            for (j=columnStart[i];
956                 j&lt;columnStart[i]+columnLength[i];j++) {
957              int iRow=row[j];
958              rowActivity2[iRow] ++; // This row redundant
959            }
960          }
961        }
962      }
963    }
964    int nOK=0; // Use to count rows which can be covered
965    int nNewRow=0; // Use to make list of rows needed
966    for (i=0;i&lt;numberRows;i++) {
967      if (rowActivity[i])
968        nOK++;
969      if (!rowActivity2[i])
970        whichRow[nNewRow++]=i; // not satisfied
971      else
972        modelPtr_-&gt;setRowStatus(i,ClpSimplex::basic); // make slack basic
973    }
974    if (nOK&lt;numberRows) {
975      // The variables we have do not cover rows - see if we can find any that do
976      for (i=0;i&lt;numberColumns;i++) {
977        if (!mark[i]&amp;&amp;upper[i]) {
978          CoinBigIndex j;
979          int good=0;
980          for (j=columnStart[i];
981               j&lt;columnStart[i]+columnLength[i];j++) {
982            int iRow=row[j];
983            if (!rowActivity[iRow]) {
984              rowActivity[iRow] ++;
985              good++;
986            }
987          }
988          if (good) {
989            nOK+=good; // This covers - put in list
990            whichColumn[nNewCol++]=i;
991          }
992        }
993      }
994    }
995    delete [] rowActivity;
996    delete [] rowActivity2;
997    if (nOK&lt;numberRows) {
998      // By inspection the problem is infeasible - no need to solve
999      modelPtr_-&gt;setProblemStatus(1);
1000      delete [] whichRow;
1001      delete [] whichColumn;
1002      printf("infeasible by inspection\n");
1003      return;
1004    }
1005    // Now make up a small model with the right rows and columns
1006    ClpSimplex *  temp = new ClpSimplex(modelPtr_,nNewRow,whichRow,nNewCol,whichColumn);
1007     
1008  </pre></div><p>
1009If the variables cover the rows, then the problem is feasible (no cuts are being used). (If the rows
1010were equality constraints, then this might not be the case. More work would be needed.)  After the solution to the subproblem, the reduced costs of the full problem are checked. If the reduced cost of any variable not in the subproblem is negative, the code goes back to the full problem and cleans up with Primal Simplex.
1011  </p><div class="example"><a id="id3422178"></a><p class="title"><b>Example 7.4. Check Optimal Solution</b></p><pre class="programlisting">
1012   
1013    temp-&gt;setDualObjectiveLimit(1.0e50); // Switch off dual cutoff as problem is restricted
1014    temp-&gt;dual(); // solve
1015    double * solution = modelPtr_-&gt;primalColumnSolution(); // put back solution
1016    const double * solution2 = temp-&gt;primalColumnSolution();
1017    memset(solution,0,numberColumns*sizeof(double));
1018    for (i=0;i&lt;nNewCol;i++) {
1019      int iColumn = whichColumn[i];
1020      solution[iColumn]=solution2[i];
1021      modelPtr_-&gt;setStatus(iColumn,temp-&gt;getStatus(i));
1022    }
1023    double * rowSolution = modelPtr_-&gt;primalRowSolution();
1024    const double * rowSolution2 = temp-&gt;primalRowSolution();
1025    double * dual = modelPtr_-&gt;dualRowSolution();
1026    const double * dual2 = temp-&gt;dualRowSolution();
1027    memset(dual,0,numberRows*sizeof(double));
1028    for (i=0;i&lt;nNewRow;i++) {
1029      int iRow=whichRow[i];
1030      modelPtr_-&gt;setRowStatus(iRow,temp-&gt;getRowStatus(i));
1031      rowSolution[iRow]=rowSolution2[i];
1032      dual[iRow]=dual2[i];
1033    }
1034    // See if optimal
1035    double * dj = modelPtr_-&gt;dualColumnSolution();
1036    // get reduced cost for large problem
1037    // this assumes minimization
1038    memcpy(dj,modelPtr_-&gt;objective(),numberColumns*sizeof(double));
1039    modelPtr_-&gt;transposeTimes(-1.0,dual,dj);
1040    modelPtr_-&gt;setObjectiveValue(temp-&gt;objectiveValue());
1041    modelPtr_-&gt;setProblemStatus(0);
1042    int nBad=0;
1043     
1044    for (i=0;i&lt;numberColumns;i++) {
1045      if (modelPtr_-&gt;getStatus(i)==ClpSimplex::atLowerBound
1046          &amp;&amp;upper[i]&gt;lower[i]&amp;&amp;dj[i]&lt;-1.0e-5)
1047        nBad++;
1048    }
1049    // If necessary clean up with primal (and save some statistics)
1050    if (nBad) {
1051      timesBad_++;
1052      modelPtr_-&gt;primal(1);
1053      iterationsBad_ += modelPtr_-&gt;numberIterations();
1054    }
1055     
1056  </pre></div><p>
1057The array <tt class="varname">node_</tt> is updated, as for the first few solves.  To give some idea of the effect of this tactic, the problem fast0507 has 63,009 variables but the small problem never has more than 4,000 variables. In only about ten percent of solves was it necessary to resolve, and then the average number of iterations
1058on full problem was less than 20.
1059</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="quadratic"></a>Quadratic MIP</h2></div></div><div></div></div><p>
1060To give another example - again only for illustrative purposes -- it is possible to do quadratic
1061MIP with CBC.  In this case, we make <tt class="function">resolve</tt> the same as
1062<tt class="function">initialSolve</tt>.
1063   The full code is in <tt class="filename">ClpQuadInterface.hpp</tt> and
1064   <tt class="filename">ClpQuadInterface.cpp</tt> located in the CBC Samples directory, see
1065  <a href="#moreexamples" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
1066More Samples
1067</i></a>).
1068  </p><div class="example"><a id="id3422245"></a><p class="title"><b>Example 7.5. Solving a Quadratic MIP</b></p><pre class="programlisting">
1069   
1070  // save cutoff
1071  double cutoff = modelPtr_-&gt;dualObjectiveLimit();
1072  modelPtr_-&gt;setDualObjectiveLimit(1.0e50);
1073  modelPtr_-&gt;scaling(0);
1074  modelPtr_-&gt;setLogLevel(0);
1075  // solve with no objective to get feasible solution
1076  setBasis(basis_,modelPtr_);
1077  modelPtr_-&gt;dual();
1078  basis_ = getBasis(modelPtr_);
1079  modelPtr_-&gt;setDualObjectiveLimit(cutoff);
1080  if (modelPtr_-&gt;problemStatus())
1081    return; // problem was infeasible
1082  // Now pass in quadratic objective
1083  ClpObjective * saveObjective  = modelPtr_-&gt;objectiveAsObject();
1084  modelPtr_-&gt;setObjectivePointer(quadraticObjective_);
1085  modelPtr_-&gt;primal(); // Th model has a quadratic objective,
1086                       // so this invokes quadratic primal.
1087  modelPtr_-&gt;setDualObjectiveLimit(cutoff);
1088  if (modelPtr_-&gt;objectiveValue()&gt;cutoff)
1089    modelPtr_-&gt;setProblemStatus(1);
1090  modelPtr_-&gt;setObjectivePointer(saveObjective);
1091     
1092  </pre></div><p>
1093Rather than implementing all the method from scratch, we based the quadratic solver <tt class="classname">ClpQuadInteface</tt> on the linear programming solver <tt class="classname">OsiClpSolverInterface</tt>. This is a convenient approach to take when prototyping ideas. After the merit of an idea is proven, the user can decide is a more serious implementation is warranted.
1094</p></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="moreexamples"></a>Chapter 8. 
1095More Samples
1096</h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#id3423737">CBC's Samples Directory</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3423737"></a>CBC's Samples Directory</h2></div></div><div></div></div><p>
1097The CBC distribution includes a number of <tt class="filename">.cpp</tt> sample files.
1098Users are encouraged to use them as starting points for their own CBC projects.
1099The files can be found in the <tt class="filename">COIN/Cbc/Samples/</tt> directory.
1100For the latest information on compiling and running these samples, please see
1101the file <tt class="filename">COIN/Cbc/Samples/INSTALL</tt>.  Most of them can be built
1102by </p><pre class="programlisting">make DRIVER=name</pre><p> which produces an executable <tt class="filename">testit</tt>.  Below is a list of
1103some of the most useful sample files with a short description for each file.
1104</p><div class="table"><a id="id3424694"></a><p class="title"><b>Table 8.1. Basic Samples</b></p><table summary="Basic Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom">
1105        Source file       
1106        </th><th align="left" valign="bottom">
1107        Description
1108        </th></tr></thead><tbody><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/minimum.cpp" target="_top"><tt class="filename">minimum.cpp</tt></a></td><td align="left" valign="top">
1109        This is a CBC "Hello, world" program.  It reads a problem
1110        in MPS file format, and solves the problem using simple branch-and-bound.
1111        </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/sample2.cpp" target="_top"><tt class="filename">sample2.cpp</tt></a></td><td align="left" valign="top">
1112        This is designed to be a file that a user could modify to get a useful
1113        driver program for his or her project.  In particular, it demonstrates
1114        the use of CGL's  preprocess functionality.
1115        It uses <tt class="function">CbcBranchUser.cpp</tt>,
1116        <tt class="function">CbcCompareUser.cpp</tt> and
1117        <tt class="function">CbcHeuristicUser.cpp</tt> 
1118        with corresponding <tt class="function">*.hpp</tt> files.
1119        </td></tr></tbody></table></div><div class="table"><a id="id3424869"></a><p class="title"><b>Table 8.2. Advanced Samples</b></p><table summary="Advanced Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom">
1120        Source file       
1121        </th><th align="left" valign="bottom">
1122        Description
1123        </th></tr></thead><tbody><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/crew.cpp" target="_top"><tt class="filename">crew.cpp</tt></a></td><td align="left" valign="top">
1124        This sample shows the use of advanced branching and a use of priorities.
1125        It uses <tt class="function">CbcCompareUser.cpp</tt>
1126        with corresponding <tt class="function">*.hpp</tt> files.
1127        </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/longthin.cpp" target="_top"><tt class="filename">longthin.cpp</tt></a></td><td align="left" valign="top">
1128        This sample shows the advanced use of a solver.  It also has coding for
1129        a greedy heuristic.
1130        The solver is given in <tt class="function">CbcSolver2.hpp</tt> and
1131        <tt class="function">CbcSolver2.cpp</tt>.
1132        The heuristic is given in <tt class="function">CbcHeuristicGreedy.hpp</tt> and
1133        <tt class="function">CbcHeuristicGreedy.cpp</tt>.
1134        It uses <tt class="function">CbcBranchUser.cpp</tt> and
1135        <tt class="function">CbcCompareUser.cpp</tt>
1136        with corresponding <tt class="function">*.hpp</tt> files.
1137        </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/qmip.cpp" target="_top"><tt class="filename">qmip.cpp</tt></a></td><td align="left" valign="top">
1138        This solves a quadratic MIP.  It is to show advanced use of a solver.
1139        The solver is given in <tt class="function">ClpQuadInterface.hpp</tt> and
1140        <tt class="function">ClpQuadInterface.cpp</tt>.
1141        It uses <tt class="function">CbcBranchUser.cpp</tt> and
1142        <tt class="function">CbcCompareUser.cpp</tt>
1143        with corresponding <tt class="function">*.hpp</tt> files.
1144        </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/sos.cpp" target="_top"><tt class="filename">sos.cpp</tt></a></td><td align="left" valign="top">
1145        This artificially creates a Special Ordered Set problem.
1146        </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/lotsize.cpp" target="_top"><tt class="filename">lotsize.cpp</tt></a></td><td align="left" valign="top">
1147        This artificially creates a Lot Sizing problem.
1148        </td></tr></tbody></table></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="messages"></a>Chapter 9. 
1149  Messages
1150  </h2></div></div><div></div></div><p>
1151  Messages and codes passed by CBC are listed in the
1152  tables below.  For a complete list, see <tt class="filename">COIN/Cbc/CbcMessages.cpp</tt>. The notation used is the same as for the <tt class="function">printf</tt> in the C programming language.
1153  </p><div class="itemizedlist"><ul type="disc"><li>
1154    <tt class="computeroutput">%s</tt> is a string
1155    </li><li>
1156    <tt class="computeroutput">%d</tt> is an integer
1157    </li><li>
1158    <tt class="computeroutput">%g</tt> or <tt class="computeroutput">%f</tt>
1159    is a floating point value
1160    </li></ul></div><p>
1161
1162  </p><p>There are several log levels. Setting the log level to be <i class="parameter"><tt>i</tt></i> produces the log messages for level <i class="parameter"><tt>i</tt></i> and all levels less than <i class="parameter"><tt>i</tt></i>.
1163 </p><div class="itemizedlist"><ul type="disc"><li>
1164    Log Level 0: Switches off all CBC messages, but one.
1165    </li><li>
1166    Log Level 1: The default. 
1167    </li><li>
1168    Log Level 2: Substantial amount of information, e.g., message 15 is generated once per node. Can be useful when the evaluation at each node is slow.
1169    </li><li>
1170    Log Level 3: Tremendous amount of information, e.g., multiple messages per node.
1171    </li></ul></div><div class="table"><a id="id3426171"></a><p class="title"><b>Table 9.1. 
1172  CBC Messages Passed At Log Level 0
1173  </b></p><table summary="&#10;  CBC Messages Passed At Log Level 0&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1174      Code
1175      </th><th> </th><th align="left">
1176      Text and notes
1177      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1178      3007
1179      </td><td> </td><td align="left"><tt class="computeroutput">No integer variables - nothing to do</tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1180
1181      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id3426316"></a><p class="title"><b>Table 9.2. 
1182  CBC Messages Passed At or Above Log Level 1
1183  </b></p><table summary="&#10;  CBC Messages Passed At or Above Log Level 1&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1184      Code
1185      </th><th> </th><th align="left">
1186      Text and notes
1187      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1188      1
1189      </td><td> </td><td align="left"><tt class="computeroutput">Search completed - best objective %g, took %d iterations and %d nodes
1190      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1191     
1192      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1193      3
1194      </td><td> </td><td align="left"><tt class="computeroutput">Exiting on maximum nodes
1195      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1196     
1197      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1198      4
1199      </td><td> </td><td align="left"><tt class="computeroutput">
1200      Integer solution of %g found after %d iterations and %d nodes
1201      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1202     
1203      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1204      5
1205      </td><td> </td><td align="left"><tt class="computeroutput">
1206      Partial search - best objective %g (best possible %g), took %d iterations and %d nodes
1207      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1208     
1209      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1210      6
1211      </td><td> </td><td align="left"><tt class="computeroutput">
1212      The LP relaxation is infeasible or too expensive
1213      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1214     
1215      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1216      9
1217      </td><td> </td><td align="left"><tt class="computeroutput">
1218      Objective coefficients multiple of %g
1219      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1220     
1221      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1222      10
1223      </td><td> </td><td align="left"><tt class="computeroutput">
1224      After %d nodes, %d on tree, %g best solution, best possible %g
1225      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1226     
1227      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1228      11
1229      </td><td> </td><td align="left"><tt class="computeroutput">
1230      Exiting as integer gap of %g less than %g or %g%%
1231      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1232           
1233      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1234      12
1235      </td><td> </td><td align="left"><tt class="computeroutput">
1236      Integer solution of %g found by heuristic after %d iterations and %d nodes
1237      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1238     
1239      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1240      13
1241      </td><td> </td><td align="left"><tt class="computeroutput">
1242      At root node, %d cuts changed objective from %g to %g in %d passes
1243      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1244     
1245      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1246      14
1247      </td><td> </td><td align="left"><tt class="computeroutput">
1248      Cut generator %d (%s) - %d row cuts (%d active), %d column cuts %? in %g seconds - new frequency is %d
1249      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1250     
1251      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1252      16
1253      </td><td> </td><td align="left"><tt class="computeroutput">
1254      Integer solution of %g found by strong branching after %d iterations and %d nodes
1255      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1256     
1257      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1258      17
1259      </td><td> </td><td align="left"><tt class="computeroutput">
1260      %d solved, %d variables fixed, %d tightened
1261      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1262     
1263      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1264      18
1265      </td><td> </td><td align="left"><tt class="computeroutput">
1266      After tightenVubs, %d variables fixed, %d tightened
1267      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1268     
1269      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1270      19
1271      </td><td> </td><td align="left"><tt class="computeroutput">
1272      Exiting on maximum solutions
1273      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1274     
1275      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1276      20
1277      </td><td> </td><td align="left"><tt class="computeroutput">
1278      Exiting on maximum time
1279      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1280     
1281      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1282      23
1283      </td><td> </td><td align="left"><tt class="computeroutput">
1284      Cutoff set to %g - equivalent to best solution of %g
1285      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1286     
1287      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1288      24
1289      </td><td> </td><td align="left"><tt class="computeroutput">
1290      Integer solution of %g found by subtree after %d iterations and %d nodes
1291      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1292     
1293      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1294      26
1295      </td><td> </td><td align="left"><tt class="computeroutput">
1296      Setting priorities for objects %d to %d inclusive (out of %d)
1297      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1298     
1299      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1300      3008
1301      </td><td> </td><td align="left"><tt class="computeroutput">
1302      Strong branching is fixing too many variables, too expensively!
1303      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1304     
1305      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id3427680"></a><p class="title"><b>Table 9.3. 
1306  CBC Messages Passed At or Above Log Level 2
1307  </b></p><table summary="&#10;  CBC Messages Passed At or Above Log Level 2&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1308      Code
1309      </th><th> </th><th align="left">
1310      Text and notes
1311      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1312      15
1313      </td><td> </td><td align="left"><tt class="computeroutput">
1314      Node %d Obj %g Unsat %d depth %d
1315      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1316     
1317      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1318      21
1319      </td><td> </td><td align="left"><tt class="computeroutput">
1320      On closer inspection node is infeasible
1321      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1322     
1323      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1324      22
1325      </td><td> </td><td align="left"><tt class="computeroutput">
1326      On closer inspection objective value of %g above cutoff of %g
1327      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1328     
1329      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1330      23
1331      </td><td> </td><td align="left"><tt class="computeroutput">
1332      Allowing solution, even though largest row infeasibility is %g
1333      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1334     
1335      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id3428080"></a><p class="title"><b>Table 9.4. 
1336  CBC Messages Passed At or Above Log Level 3
1337  </b></p><table summary="&#10;  CBC Messages Passed At or Above Log Level 3&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1338      Code
1339      </th><th> </th><th align="left">
1340      Text and notes
1341      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1342      7
1343      </td><td> </td><td align="left"><tt class="computeroutput">
1344      Strong branching on %d (%d), down %g (%d) up %g (%d) value %g
1345      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1346     
1347      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1348      25
1349      </td><td> </td><td align="left"><tt class="computeroutput">
1350      %d cleanup iterations before strong branching
1351      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1352     
1353      </p></td><td class="auto-generated"> </td></tr></tbody></table></div></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="id3430230"></a>Appendix A. FAQ</h2></div></div><div></div></div><div class="qandaset"><table border="0" summary="Q and A Set"><col align="left" width="1%" /><tbody><tr class="question"><td align="left" valign="top"><a id="id3429594"></a><a id="id3430253"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1354  What is <a href="https://projects.coin-or.org/Cbc/wiki/FAQ" target="_top">CBC</a>?
1355  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1356  The <a href="http://www.coin-or.org/" target="_top">COIN-OR</a> Branch and Cut code
1357  is designed to be a high quality mixed integer code provided under the terms of the
1358  <a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public License</a>.
1359  CBC is written in C++, and is primarily intended to be used as a callable
1360  library (though a rudimentary stand-alone executable exists).
1361  The first documented release was .90.0  The current release is version .90.0. (JF 04/01/05)
1362  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3430308"></a><a id="id3430312"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1363  What are some of the features of CBC?
1364  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1365  CBC allows the use of any CGL cuts and the use of heuristics and
1366   specialized branching methods. (JF 04/01/05)
1367  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431247"></a><a id="id3431250"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1368  How do I obtain and install CBC?
1369  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1370  Please see the
1371  <a href="http://www.coin-or.org/faqs.html" target="_top">COIN-OR FAQ</a>
1372  for details on how to
1373  <a href="http://www.coin-or.org/faqs.html#ObtainSrcCode" target="_top">obtain</a>
1374  and
1375  <a href="http://www.coin-or.org/faqs.html#BuildCode" target="_top">install</a>
1376  COIN-OR modules. (JF 04/01/05)
1377  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431296"></a><a id="id3431300"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1378  Is CBC reliable?
1379  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1380  CBC has been tested on many problems,
1381  but more testing and improvement is needed before it can get to version 1.0. (JF 04/01/05)
1382  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431322"></a><a id="id3431325"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1383  Is there any documentation for CBC? 
1384  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1385  If you can see this you have the best there is:-)
1386  Also available is a list of
1387  <a href="http://www.coin-or.org/Doxygen/Cbc/" target="_top">CBC class descriptions</a> generated
1388  by <a href="http://www.doxygen.org" target="_top">Doxygen</a>. (JF 04/01/05)
1389  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431364"></a><a id="id3431367"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1390  Is CBC as fast as Cplex or Xpress?
1391  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1392   No. However its design is much more flexible so advanced users
1393   will be able to tailor CBC to their needs. (JF 04/01/05)
1394  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431390"></a><a id="id3431393"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1395  When will version 1.0 of CBC be available? 
1396  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1397  It is expected that version 1.0 will be released in time for the 2005
1398  <a href="http://www.informs.org" target="_top">INFORMS</a> annual meeting. (JF 04/01/05)
1399  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3431423"></a><a id="id3431426"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1400  What can the community do to help?
1401  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1402  People from all around the world are already helping.  There are
1403  probably ten people who do not always post to the discussion mail list but are constantly
1404  "improving" the code by demanding performance or bug fixes or enhancements.  And there
1405  are others posting questions to discussion groups. (JF 04/01/05)
1406  </p><p>
1407  A good start is to join the coin-discuss
1408  <a href="http://www.coin-or.org/mail.html" target="_top">mailing list</a> where CBC is discussed.  Some
1409  other possibilities include:
1410  </p><div class="itemizedlist"><ul type="disc"><li><p>
1411  Comment on the design
1412  </p></li><li><p>
1413  Give feedback on the documentation and FAQs.
1414  </p></li><li><p>
1415  Break the code, or better yet -- mend it.
1416  </p></li><li><p>
1417  Tackle any of the "to-dos" listed in the Doxyen documentation and contribute back to COIN-OR.
1418  </p></li></ul></div></td></tr></tbody></table></div></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="doxygen"></a>Appendix B. Doxygen</h2></div></div><div></div></div><p>
1419There is Doxygen content for CBC available online at
1420<a href="http://www.coin-or.org/Doxygen/Cbc/index.html" target="_top">
1421http://www.coin-or.org/Doxygen/Cbc/index.html</a>.  A local version of the
1422Doxygen content can be generated from the CBC distribution.  To do so, in the
1423directory <tt class="filename">COIN/Cbc</tt>, enter <b class="userinput"><tt>make doc</tt></b>.
1424The Doxygen content will be created in the directory
1425<tt class="filename">COIN/Cbc/Doc/html</tt>.  The same can be done for
1426the COIN core, from the <tt class="filename">COIN/Coin</tt> directory.
1427</p></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="id3429980"></a>Appendix C. Revision History</h2></div></div><div></div></div><div class="revhistory"><table border="0" width="100%" summary="Revision history"><tr><th align="left" valign="top" colspan="3"><b>Revision History</b></th></tr><tr><td align="left">Revision 0.21</td><td align="left">May 10, 2005</td><td align="left">RLH</td></tr><tr><td align="left" colspan="3">Fixed typos caught by Cole Smith, editor of the INFORMS Tutorial Book, and added place holders for needs-to-be-written sections, e.g., Using CGL with CBC.</td></tr><tr><td align="left">Revision 0.2</td><td align="left">May 2, 2005</td><td align="left">RLH</td></tr><tr><td align="left" colspan="3">Book chapter for CBC Tutorial at INFORMS 2005 annual meeting. Reorganized the content. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.</td></tr><tr><td align="left">Revision 0.1</td><td align="left">April 1, 2005</td><td align="left">JF</td></tr><tr><td align="left" colspan="3">First draft. The CBC documentation uses the DocBook CLP documentation created by David de la Nuez.</td></tr></table></div></div></div></body></html>
Note: See TracBrowser for help on using the repository browser.