source: html/trunk/Cbc/cbcuserguide.html @ 555

Last change on this file since 555 was 555, checked in by rlh, 15 years ago

* empty log message *

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 100.9 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="#id2887266">
30  Welcome to CBC
31  </a></dt><dt><a href="#id2887095">
32  Prerequisites
33  </a></dt><dt><a href="#id2886977">
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="#branching">Pseudo Cost Branching</a></dt><dt><a href="#followOn">Follow-On Branching</a></dt></dl></dd><dt>6. <a href="#SolverChap">
56  Advance 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>7. <a href="#moreexamples">
58More Samples
59</a></dt><dd><dl><dt><a href="#id2968762">CBC's Samples Directory</a></dt></dl></dd><dt>8. <a href="#messages">
60  Messages
61  </a></dt><dt>A. <a href="#id2974565">FAQ</a></dt><dt>B. <a href="#doxygen">Doxygen</a></dt><dt>C. <a href="#id2974315">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="#id2959780">
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="#id2961253">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>7.1. <a href="#id2969026">Basic Samples</a></dt><dt>7.2. <a href="#id2969203">Advanced Samples</a></dt><dt>8.1. <a href="#id2970505">
64  CBC Messages Passed At Logging Level 0
65  </a></dt><dt>8.2. <a href="#id2970650">
66  CBC Messages Passed At or Above Logging Level 1
67  </a></dt><dt>8.3. <a href="#id2972014">
68  CBC Messages Passed At or Above Logging Level 2
69  </a></dt><dt>8.4. <a href="#id2972415">
70  CBC Messages Passed At or Above Logging 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="#id2966006">Data</a></dt><dt>4.2. <a href="#id2966036">Initialize newSolution</a></dt><dt>4.3. <a href="#id2966116">Create Feasible newSolution from Initial newSolution</a></dt><dt>4.4. <a href="#id2966155">Check Solution Quality of newSolution</a></dt><dt>5.1. <a href="#pseudo">CbcSimpleIntegerPseudoCosts</a></dt><dt>5.2. <a href="#id2966435">CbcFollowOn</a></dt><dt>6.1. <a href="#initialSolve">initialSolve()</a></dt><dt>6.2. <a href="#id2966664">First Few Solves</a></dt><dt>6.3. <a href="#id2966692">Create Small Problem</a></dt><dt>6.4. <a href="#id2966737">Check Optimal Solution</a></dt><dt>6.5. <a href="#id2966802">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="#id2887266">
74  Welcome to CBC
75  </a></dt><dt><a href="#id2887095">
76  Prerequisites
77  </a></dt><dt><a href="#id2886977">
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="id2887266"></a>
80  Welcome to CBC
81  </h2></div></div><div></div></div><p>
82  The COIN
83    <sup>[<a id="id2887276" href="#ftn.id2887276">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="id2887095"></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> and
93  <a href="http://carbon.cudenver.edu/~hgreenbe/courseware/MIP/intro.html" target="_top">
94  mixed integer programming</a>.
95  </p><p>
96
97CBC relies other parts of the COIN repository. CBC needs an LP solver and relies 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 assesses 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>
104    C++ knowledge,
105    </li><li>
106    LP and MIP fundamentals, and   
107    </li><li>
108    OSI familiarity.
109    </li></ul></div><p>
110</p><p>
111Unless otherwise stated, we will assume the problem being optimized is a minimization problem. The terms "model" and "problem" are used synonymously.
112</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2886977"></a>
113Branch-and-Cut Overview
114</h2></div></div><div></div></div><p>
115  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>.
116 </p><p>
117Step 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.   
118 </p><p> 
119Step 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 nodes, 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 
142  </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>
143    Note
144    </th><th>
145    Class name
146    </th><th>
147    Description
148    </th></tr></thead><tbody><tr><td align="left" valign="top">
149      (A)
150      </td><td align="left" valign="top"><tt class="classname">CbcBranch...</tt></td><td align="left" valign="top">
151      These classes define the nature of MIP's discontinuity.  The simplest discontinuity
152      is a variable which must take an integral value. Other types of discontinuities
153      exist, e.g., lot-sizing variables.
154      </td></tr><tr><td align="left" valign="top">
155      (B)
156      </td><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top">
157      This class decides which variable/entity to branch on next.
158      Even advanced users will probably only interact with this class by setting
159      <tt class="classname">CbcModel</tt> parameters ( e.g., priorities).
160      </td></tr><tr><td align="left" valign="top">
161      (C)
162      </td><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top">
163      All unsolved models can be thought of as being nodes on a tree where each
164      node (model) can branch two or more times.  The user should not need to be
165      concerned with this class.
166      </td></tr><tr><td align="left" valign="top">
167      (D)
168      </td><td align="left" valign="top"><tt class="classname">CbcCompare...</tt></td><td align="left" valign="top">
169      These classes are used in determine which of the unexplored nodes in the tree to consider next. These
170      classes are very small simple classes that can be tailored to suit the problem.
171      </td></tr><tr><td align="left" valign="top">
172      (E)
173      </td><td align="left" valign="top"><tt class="classname">CglCutGenerators</tt></td><td align="left" valign="top">
174      Any cut generator from CGL can be used in CBC. The cut generators are passed to CBC with parameters
175      which modify when each generator will be tried. All cut generators should be tried to
176      determine which are effective. Few users will write their own cut generators.
177      </td></tr><tr><td align="left" valign="top">
178      (F)
179      </td><td align="left" valign="top"><tt class="classname">CbcHeuristics</tt></td><td align="left" valign="top">
180      Heuristics are very important for obtaining valid solutions quickly.  Some
181      heuristics are available, but this is an area where it is useful and interesting to
182      write specialized ones.
183      </td></tr></tbody></table></div><p>
184  There are a number of resources available to help new CBC users get started.
185  This document is designed to be used in conjunction with the files in the
186  Samples subdirectory of the main CBC directory (<tt class="filename">COIN/Cbc/Samples</tt>).
187  The Samples illustrate how to use CBC and may also serve as useful starting points
188  for user projects.  In the event that either this document or the available
189  <a href="#doxygen" title="Appendix B. Doxygen">Doxygen content</a> conflicts with the observed
190  behavior of the source code, the comments in the header files, found in
191  <tt class="filename">COIN/Cbc/include</tt>, are the ultimate reference.
192  </p></div><div class="footnotes"><br /><hr width="100" align="left" /><div class="footnote"><p><sup>[<a id="ftn.id2887276" href="#id2887276">1</a>] </sup>
193        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".
194        </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. 
195   The CBC Model Class
196  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#hierarchy">
197  Overview
198  </a></dt><dt><a href="#firstexample">
199  Simple Branch-and-Bound Example
200  </a></dt><dt><a href="#osiAndCbc">
201The Relationship Between OSI and CBC
202</a></dt><dt><a href="#gettingsolution">
203  Getting Solution Information
204  </a></dt><dt><a href="#setsandgets">
205   Useful Set and Get Methods in CbcModel
206  </a></dt><dt><a href="#majormethods">
207  Impacting the Solution Process
208  </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>
209  Overview
210  </h2></div></div><div></div></div><p>
211  The main class in CBC is <tt class="classname">CbcModel</tt>.  The <tt class="classname">CbcModel</tt> class is where most
212  of the parameter setting is done. The absolute minimum number of actions taken with <tt class="classname">CbcModel</tt> is two,
213    </p><div class="itemizedlist"><ul type="disc"><li>
214    <tt class="function">CbcModel(OsiSolverInterface &amp; linearSolver)</tt> as constructor, and
215    </li><li>
216    <tt class="function">branchAndBound()</tt> for solving the problem.   
217    </li></ul></div><p>
218  </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>
219  Simple Branch-and-Bound Example
220  </h2></div></div><div></div></div><p>
221  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.
222  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>.
223
224  </p><div class="example"><a id="minimum.cpp"></a><p class="title"><b>Example 2.1. minimum.cpp</b></p><pre class="programlisting">
225   
226// Copyright (C) 2005, International Business Machines
227// Corporation and others.  All Rights Reserved.
228
229#include "CbcModel.hpp"
230
231// Using CLP as the solver
232#include "OsiClpSolverInterface.hpp"
233
234int main (int argc, const char *argv[])
235{
236  OsiClpSolverInterface solver1;
237
238  // Read in example model in MPS file format
239  // and assert that it is a clean model
240  int numMpsReadErrors = solver1.readMps("../../Mps/Sample/p0033.mps","");
241  assert(numMpsReadErrors==0);
242
243  // Pass the solver with the problem to be solved to CbcModel
244  CbcModel model(solver1);
245
246  // Do complete search
247  model.branchAndBound();
248
249  /* Print the solution.  CbcModel clones the solver so we
250     need to get current copy from the CbcModel */
251  int numberColumns = model.solver()-&gt;getNumCols();
252   
253  const double * solution = model.solver()-&gt;getColSolution();
254   
255  for (int iColumn=0;iColumn&lt;numberColumns;iColumn++) {
256    double value=solution[iColumn];
257    if (fabs(value)&gt;1.0e-7&amp;&amp;model.solver()-&gt;isInteger(iColumn))
258      printf("%d has value %g\n",iColumn,value);
259   }
260  return 0;
261}   
262     
263  </pre></div><p>
264  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.
265 </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>
266The Relationship Between OSI and CBC
267</h2></div></div><div></div></div><p> 
268The program in <a href="#minimum.cpp" title="Example 2.1. minimum.cpp">Example 2.1</a> illustrates the dependency of CBC on 
269  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> method.  To synchronize the two solvers, explicitly refreshing the original, e.g., 
270 </p><pre class="programlisting">
271  solver1 = model.solver();
272</pre><p>
273<tt class="classname">CbcModel</tt>'s method <tt class="function">solve()</tt> returns a pointer to CBC's cloned solver.
274</p><p>
275For 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 OSI method <tt class="function">getColSolution()</tt> will contain the best solution so far, while the <tt class="classname">CbcModel</tt> method may not. In this case, it is safer to use <tt class="function">CbcModel::bestSolution()</tt>.
276</p><p>
277While 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
278</p><pre class="programlisting">
279  model.solver()-&gt;setHintParam(OsiDoReducePrint,true,OsiHintTry);
280</pre><p> 
281 
282  to reduce the output. There is no <tt class="function">setHintParam()</tt> method in <tt class="classname">CbcModel</tt>.
283  </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>
284  Getting Solution Information
285  </h2></div></div><div></div></div><p>
286  Optimality can be checked through a call to <tt class="function">model.isProvenOptimal()</tt>.  Also
287  available are <tt class="function">isProvenInfeasible()</tt>,
288  <tt class="function">isSolutionLimitReached()</tt>,
289  <tt class="function">isNodeLimitReached()</tt> or the feared
290  <tt class="function">isAbandoned()</tt>. There is also
291  <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.
292  </p><p>
293  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.
294  </p><div class="table"><a id="id2959780"></a><p class="title"><b>Table 2.1. 
295  Methods for Getting Solution Information from OSI
296  </b></p><table summary="&#10;  Methods for Getting Solution Information from OSI &#10;  " border="0"><colgroup><col /><col /></colgroup><thead><tr><th>
297      Purpose
298      </th><th>
299      Name
300      </th><th>
301      Notes
302      </th></tr></thead><tbody><tr><td align="left" valign="top">
303      Primal column solution
304      </td><td align="left" valign="top"><tt class="function">const double * getColSolution()</tt></td><td align="left" valign="top">
305      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">
306      Dual row solution
307      </td><td align="left" valign="top"><tt class="function">const double * getRowPrice()</tt></td><td align="left" valign="top">
308      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowPrice()</tt>.
309      </td></tr><tr><td align="left" valign="top">
310      Primal row solution
311      </td><td align="left" valign="top"><tt class="function">const double * getRowActivity()</tt></td><td align="left" valign="top">
312      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowActivity()</tt>.
313      </td></tr><tr><td align="left" valign="top">
314      Dual column solution
315      </td><td align="left" valign="top"><tt class="function">const double * getReducedCost()</tt></td><td align="left" valign="top">
316      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::gtReducedCost()</tt>.
317      </td></tr><tr><td align="left" valign="top">
318      Number of rows in model
319      </td><td align="left" valign="top"><tt class="function">int getNumRows()</tt></td><td align="left" valign="top">
320      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumRows()</tt>. Note: the number of rows can change due to cuts.
321      </td></tr><tr><td align="left" valign="top">
322      Number of columns in model
323      </td><td align="left" valign="top"><tt class="function">int getNumCols()</tt></td><td align="left" valign="top">
324      Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumCols()</tt>.
325      </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>
326   Useful Set and Get Methods in <tt class="classname">CbcModel</tt>
327  </h2></div></div><div></div></div><p>
328Most 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>.
329</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>
330    Method(s)
331    </th><th>
332    Description
333    </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">
334      These set methods tell CBC to stop after a given number of nodes,
335      seconds, or solutions is reached. The get methods return the corresponding values.
336      </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">
337      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.
338      </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
339      possible solution is less than this <i class="parameter"><tt>value</tt></i>, or as a percentage, or a fraction.
340      </td></tr><tr><td align="left" valign="top"><tt class="function">void setNumberStrong(double value) </tt><br /><tt class="function">int numberStrong() const </tt></td><td align="left" valign="top">
341      These methods set or get the maximum number of candidates at a node to
342      be evaluated for strong branching.
343      </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">
344      Controls the number of nodes evaluated between status prints.
345      Print frequency has a very slight overhead, if <i class="parameter"><tt>value</tt></i> is small.
346      </td></tr><tr><td align="left" valign="top"><tt class="function">int getNodeCount() const</tt></td><td align="left" valign="top">
347      Returns number of nodes evaluated in the search.
348      </td></tr><tr><td align="left" valign="top"><tt class="function">int numberRowsAtContinuous() const</tt></td><td align="left" valign="top">
349      Returns number of rows at continuous </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">
350      Returns number of integer variables and an array specifying them.
351      </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">
352      Returns information on variable <i class="parameter"><tt>colIndex</tt></i>. OSI methods
353      can be used to set these attributes (before handing the model to <tt class="classname">CbcModel</tt>).
354      </td></tr><tr><td align="left" valign="top"><tt class="function">double getObjValue() const</tt></td><td align="left" valign="top">
355      This method returns the best objective value so far.
356      </td></tr><tr><td align="left" valign="top"><tt class="function">double getCurrentObjValue() const</tt></td><td align="left" valign="top">
357      This method returns the current objective value.
358      </td></tr><tr><td align="left" valign="top"><tt class="function">const double * getObjCoefficients() const</tt><br /></td><td align="left" valign="top">
359      This method return the objective coefficients.
360      </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">
361      These methods return the lower and upper bounds on row and column activities.
362      </td></tr><tr><td align="left" valign="top"><tt class="function">const CoinPackMatrix * getMatrixByRow() const</tt></td><td align="left" valign="top">
363      This method returns a pointer to a row copy of matrix stored as a
364      <tt class="classname">CoinPackedMatrix</tt> which can be further examined.
365      </td></tr><tr><td align="left" valign="top"><tt class="function">const CoinPackMatrix * getMatrixByCol() const</tt></td><td align="left" valign="top">
366      This method returns a pointer to a column 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">CoinBigIndex getNumElements() const</tt><sup>[<a id="id2961056" href="#ftn.id2961056">a</a>]</sup></td><td align="left" valign="top">
369      Returns the number of nonzero elements in the problem matrix.
370      </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">
371      These methods set and get the objective sense.  The parameter
372      <i class="parameter"><tt>value</tt></i> should be +1 to minimize and -1 to maximize.
373      </td></tr></tbody><tbody class="footnotes"><tr><td colspan="2"><div class="footnote"><p><sup>[<a id="ftn.id2961056" href="#id2961056">a</a>] </sup> 
374        <span class="type">CoinBigIndex</span> is a <tt class="function">typedef</tt> which in
375        most cases is the same as <span class="type">int</span>.
376        </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>
377  Impacting the Solution Process
378  </h2></div></div><div></div></div><p>
379<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:
380    </p><div class="itemizedlist"><ul type="disc"><li>
381     selecting the next node to consider in the search tree,
382    </li><li>
383    determining which variable to branch on,
384    </li><li>
385    using heuristics to generate MIP-feasible solutions quickly,
386    </li><li>
387    including cut generation when solving the LP-relaxations, and
388    </li><li>
389    invoking customized subproblem solvers.
390    </li></ul></div><p>
391
392
393To 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.
394</p><div class="table"><a id="id2961253"></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>
395    Class name
396    </th><th>
397    Description
398    </th><th>
399    Notes
400    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareBase</tt></td><td align="left" valign="top">
401      Controls which node on the tree is selected.
402      </td><td align="left" valign="top">
403      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.
404      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCutGenerator</tt></td><td align="left" valign="top">
405      A wrapper for <tt class="classname">CglCutGenerator</tt> with additional data to control when the cut generator is invoked during the tree search.
406      </td><td align="left" valign="top">
407      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">
408      Heuristic that attempts to generate valid MIP-solutions leading to good upper bounds.
409      </td><td align="left" valign="top">
410      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">
411      Defines what it means for a variable to be satisfied. Used in branching.
412      </td><td align="left" valign="top">
413      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 comparsion 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>.
414      </td></tr><tr><td align="left" valign="top"><tt class="classname">OsiSolverInterface</tt></td><td align="left" valign="top">
415      Defines the LP solver being used and the LP model. Normally
416      a pointer to the desired <tt class="classname">OsiSolverInteface</tt> is passed to <tt class="classname">CbcModel</tt> before branch and cut.
417      </td><td align="left" valign="top">
418      Virtual class. The user instantiates the solver interface of their choice, e.g.,
419      <tt class="classname">OsiClpSolverInterface</tt>.
420      </td></tr></tbody></table></div><p>
421There 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.
422</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>
423    Class name
424    </th><th>
425    Description
426    </th><th>
427    Notes
428    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcBranchDecision</tt></td><td align="left" valign="top">
429      Used in choosing which variable to branch on, however, most of
430      the work is done by the definitions in <tt class="classname">CbcObject</tt>.
431      </td><td align="left" valign="top">
432      Defaults to <tt class="classname">CbcBranchDefaultDecision</tt>.
433      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCountRowCut</tt></td><td align="left" valign="top">
434      Interface to <tt class="classname">OsiRowCut</tt>. It counts the usage so cuts can gracefully vanish.
435      </td><td align="left" valign="top">
436      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">
437      Controls which variable/entity is selected to be branch on.
438      </td><td align="left" valign="top">
439      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">
440      Contains data on bounds, basis, etc. for one node of the search tree.
441      </td><td align="left" valign="top">
442      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">
443      Defines how the search tree is stored.
444      </td><td align="left" valign="top">
445      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">
446      Deals with message handling
447      </td><td align="left" valign="top">
448      The user can inherit from <tt class="classname">CoinMessageHandler</tt> to specialize message handling. 
449      </td></tr><tr><td align="left" valign="top"><tt class="classname">CoinWarmStartBasis</tt></td><td align="left" valign="top">
450      Basis representation to be used by solver
451      </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. 
452  Selecting the Next Node in the Search Tree
453  </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>
454  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. The search order is controlled via the <tt class="classname">CbcCompare...</tt> class. CBC provides an abstract base class, <tt class="classname">CbcCompareBase</tt>,  and several commonly used instances which are described in <a href="#compareTable" title="Table 3.1. Compare Classes Provided">Table 3.1</a>.
455  </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>
456    Class name
457    </th><th>
458    Description
459    </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareDepth</tt></td><td align="left" valign="top">
460      This will always choose the node deepest in tree.  It gives minimum
461      tree size but may take a long time to find the best solution.
462      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareObjective</tt></td><td align="left" valign="top">
463      This will always choose the node with the best objective value.  This may
464      give a very large tree.  It is likely that the first solution found
465      will be the best and the search should finish soon after the first solution
466      is found.
467      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareDefault</tt></td><td align="left" valign="top">
468      This is designed to do a mostly depth-first search until a solution has
469      been found. It then use estimates that are designed to give a slightly better solution.
470      If a reasonable number of nodes have been explored (or a reasonable number of
471      solutions found), then this class will adopt a breadth-first search (i.e., making a comparison based strictly on objective function values) unless the tree is very large when it will revert to depth-first search. A better description of <tt class="classname">CbcCompareUser</tt> is given below.
472      </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareEstimate</tt></td><td align="left" valign="top">
473      When pseudo costs are invoked, they can be used to guess a solution.  This class uses the guessed solution.
474      </td></tr></tbody></table></div><p>
475  It is relatively simple for an experienced user to create 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. See <a href="#moreexamples" title="Chapter 7. &#10;More Samples&#10;">Chapter 7, <i>
476More Samples
477</i></a>. The key method 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> list some commonly used methods to access information at a node.
478  </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">
479      Value of objective at the node.
480      </td></tr><tr><td align="left" valign="top"><tt class="function">int numberUnsatisfied() const</tt></td><td align="left" valign="top">
481      Number of unsatisfied integers (assuming branching
482      object is an integer - otherwise it might be number of unsatisfied sets).
483      </td></tr><tr><td align="left" valign="top"><tt class="function">int depth() const</tt></td><td align="left" valign="top">
484       Depth of the node in the search tree.
485      </td></tr><tr><td align="left" valign="top"><tt class="function">double guessedObjectiveValue() const</tt></td><td align="left" valign="top"> 
486     If user was setting this (e.g., if using pseudo costs).
487      </td></tr><tr><td align="left" valign="top"><tt class="function">int way() const</tt></td><td align="left" valign="top">
488       The way which branching would next occur from this node
489       (for more advanced use).
490      </td></tr><tr><td align="left" valign="top"><tt class="function">int variable() const</tt></td><td align="left" valign="top">
491       The branching "variable" (associated with the <tt class="classname">CbcBranchingObject</tt> -- for more advanced use).
492      </td></tr></tbody></table></div><p>
493</p><p>
494The 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
495  <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
496  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.
497</p><div class="itemizedlist"><ul type="disc"><li><p>
4981) The number of solutions found so far
499  </p></li><li><p>
5002) The size of the tree (defined to be the number of active nodes)
501  </p></li><li><p>
5023) A weight, <tt class="varname">weight_</tt>, which is initialized to -1.0
503  </p></li><li><p>
5044) A saved value of weight, <tt class="varname">saveWeight_</tt> (for when weight is set back to -1.0 for special reason)
505  </p></li></ul></div><p>
506The 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>.
507</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">
508   
509// Returns true if y better than x
510bool
511CbcCompareUser::test (CbcNode * x, CbcNode * y)
512{
513  if (weight_==-1.0) {
514    // before solution
515    if (x-&gt;numberUnsatisfied() &gt; y-&gt;numberUnsatisfied())
516      return true;
517    else if (x-&gt;numberUnsatisfied() &lt; y-&gt;numberUnsatisfied())
518      return false;
519    else
520      return x-&gt;depth() &lt; y-&gt;depth();
521  } else {
522    // after solution.
523    // note: if weight_=0, comparison is based
524    //       solely on objective value
525    double weight = CoinMax(weight_,0.0);
526    return x-&gt;objectiveValue()+ weight*x-&gt;numberUnsatisfied() &gt; 
527      y-&gt;objectiveValue() + weight*y-&gt;numberUnsatisfied();
528  }
529}
530     
531  </pre></div><p>
532Initially, <tt class="varname">weight</tt>_ is -1.0 and the search is biased towards depth first.  In
533fact, <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. Once a solution is found, <tt class="function">newSolution()</tt> is called. 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>.
534</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">
535   
536// This allows the test() method to change behavior by resetting weight_.
537// It is called after each new solution is found.
538void
539CbcCompareUser::newSolution(CbcModel * model,
540                               double objectiveAtContinuous,
541                               int numberInfeasibilitiesAtContinuous)
542{
543  if (model-&gt;getSolutionCount()==model-&gt;getNumberHeuristicSolutions())
544    return; // solution was found by rounding so ignore it.
545
546  // set weight_ to get close to this solution
547  double costPerInteger =
548    (model-&gt;getObjValue()-objectiveAtContinuous)/
549    ((double) numberInfeasibilitiesAtContinuous);
550  weight_ = 0.98*costPerInteger;
551  saveWeight_=weight_;
552  numberSolutions_++;
553  if (numberSolutions_&gt;5)
554    weight_ =0.0; // comparison in test() will be
555                  // based strictly on objective value.
556}
557     
558  </pre></div><p>
559
560As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been genereated, 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>.
561  </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">
562   
563// This allows the test() method to change behavior every so often
564bool
565CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
566{
567  if (numberNodes&gt;10000)
568    weight_ =0.0; // compare nodes based on objective value
569  else if (numberNodes==1000&amp;&amp;weight_==-2.0)
570    weight_=-1.0; // Go to depth first
571  // get size of tree
572  treeSize_ = model-&gt;tree()-&gt;size();
573  if (treeSize_&gt;10000) {
574    // set weight to reduce size most of time
575    if (treeSize_&gt;20000)
576      weight_=-1.0;
577    else if ((numberNodes%4000)!=0)
578      weight_=-1.0;
579    else
580      weight_=saveWeight_;
581  }
582  return numberNodes==11000; // resort if first time
583}
584     
585  </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. 
586  Getting Good Bounds in CBC
587  </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>
588  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
589  on very large problems where a complete search is impossible.  Obviously, heuristics are
590  problem dependent, although some do have more general use.
591  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>
592  directory.  A heuristic tries to obtain a solution to the original
593  problem so it only needs to consider the original rows and does not have to use the
594  current bounds. CBC provides an abstract base class <tt class="classname">CbcHeuristic</tt> and a rounding heuristic in CBC.
595  </p><p>
596  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 7. &#10;More Samples&#10;">Chapter 7, <i>
597More Samples
598</i></a>.
599</p><p>
600  The greedy heuristic will leave all variables taking value one at this node of the
601  tree at value one, and will initially set all other variable to value zero. 
602  All variables are then sorted in order of their cost
603  divided by the number of entries in rows which are not yet covered. (We may randomize that
604  value a bit so that ties will be broken in different ways on different runs of the heuristic.)
605  The best one is choosen, and set to one. The process is repeated. Because this is
606  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).
607</p><p>
608  The key <tt class="classname">CbcHeuristic</tt> method is <tt class="function">int solution(double &amp; solutionValue,
609                                              double * betterSolution)</tt>.
610  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.
611  </p><div class="example"><a id="id2966006"></a><p class="title"><b>Example 4.1. Data</b></p><pre class="programlisting">
612   
613  OsiSolverInterface * solver = model_-&gt;solver(); // Get solver from CbcModel
614  const double * columnLower = solver-&gt;getColLower(); // Column Bounds
615  const double * columnUpper = solver-&gt;getColUpper();
616  const double * rowLower = solver-&gt;getRowLower(); // We know we only need lower bounds
617  const double * solution = solver-&gt;getColSolution();
618  const double * objective = solver-&gt;getObjCoefficients(); // In code we also use min/max
619  double integerTolerance = model_-&gt;getDblParam(CbcModel::CbcIntegerTolerance);
620  double primalTolerance;
621  solver-&gt;getDblParam(OsiPrimalTolerance,primalTolerance);
622  int numberRows = originalNumberRows_; // This is number of rows when matrix was passed in
623  // Column copy of matrix (before cuts)
624  const double * element = matrix_.getElements();
625  const int * row = matrix_.getIndices();
626  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
627  const int * columnLength = matrix_.getVectorLengths();
628
629  // Get solution array for heuristic solution
630  int numberColumns = solver-&gt;getNumCols();
631  double * newSolution = new double [numberColumns];
632  // And to sum row activities
633  double * rowActivity = new double[numberRows];
634     
635  </pre></div><p>
636The <tt class="varname">newSolution</tt> is then initialized to the rounded down solution.
637</p><div class="example"><a id="id2966036"></a><p class="title"><b>Example 4.2. Initialize <tt class="varname">newSolution</tt></b></p><pre class="programlisting">
638   
639  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
640    CoinBigIndex j;
641    double value = solution[iColumn];
642    // Round down integer
643    if (fabs(floor(value+0.5)-value)&lt;integerTolerance)
644      value=floor(CoinMax(value+1.0e-3,columnLower[iColumn]));
645    // make sure clean
646    value = CoinMin(value,columnUpper[iColumn]);
647    value = CoinMax(value,columnLower[iColumn]);
648    newSolution[iColumn]=value;
649    if (value) {
650      double cost = direction * objective[iColumn];
651      newSolutionValue += value*cost;
652      for (j=columnStart[iColumn];
653           j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
654        int iRow=row[j];
655        rowActivity[iRow] += value*element[j];
656      }
657    }
658  }
659     
660  </pre></div><p>
661
662
663At this point some row activities may be below their lower bound. To correct this 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. (Theimplementation could be faster, but is kept simple for illustrative purposes.)
664  </p><div class="example"><a id="id2966116"></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">
665   
666  while (true) {
667    // Get column with best ratio
668    int bestColumn=-1;
669    double bestRatio=COIN_DBL_MAX;
670    for (int iColumn=0;iColumn&lt;numberColumns;iColumn++) {
671      CoinBigIndex j;
672      double value = newSolution[iColumn];
673      double cost = direction * objective[iColumn];
674      // we could use original upper rather than current
675      if (value+0.99&lt;columnUpper[iColumn]) {
676        double sum=0.0; // Compute how much we will reduce infeasibility by
677        for (j=columnStart[iColumn];
678             j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
679          int iRow=row[j];
680          double gap = rowLower[iRow]-rowActivity[iRow];
681          if (gap&gt;1.0e-7) {
682            sum += CoinMin(element[j],gap);
683          if (element[j]+rowActivity[iRow]&lt;rowLower[iRow]+1.0e-7) {
684            sum += element[j];
685          }
686        }
687        if (sum&gt;0.0) {
688          double ratio = (cost/sum)*(1.0+0.1*CoinDrand48());
689          if (ratio&lt;bestRatio) {
690            bestRatio=ratio;
691            bestColumn=iColumn;
692          }
693        }
694      }
695    }
696    if (bestColumn&lt;0)
697      break; // we have finished
698    // Increase chosen column
699    newSolution[bestColumn] += 1.0;
700    double cost = direction * objective[bestColumn];
701    newSolutionValue += cost;
702    for (CoinBigIndex j=columnStart[bestColumn];
703         j&lt;columnStart[bestColumn]+columnLength[bestColumn];j++) {
704      int iRow = row[j];
705      rowActivity[iRow] += element[j];
706    }
707  }
708     
709  </pre></div><p>
710A 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.
711  </p><div class="example"><a id="id2966155"></a><p class="title"><b>Example 4.4. Check Solution Quality of <tt class="varname">newSolution</tt></b></p><pre class="programlisting">
712   
713  returnCode=0; // 0 means no good solution
714  if (newSolutionValue&lt;solutionValue) { // minimization
715    // check feasible
716    memset(rowActivity,0,numberRows*sizeof(double));
717    for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
718      CoinBigIndex j;
719      double value = newSolution[iColumn];
720      if (value) {
721        for (j=columnStart[iColumn];
722             j&lt;columnStart[iColumn]+columnLength[iColumn];j++) {
723          int iRow=row[j];
724          rowActivity[iRow] += value*element[j];
725        }
726      }
727    }
728    // check was approximately feasible
729    bool feasible=true;
730    for (iRow=0;iRow&lt;numberRows;iRow++) {
731      if(rowActivity[iRow]&lt;rowLower[iRow]) {
732        if (rowActivity[iRow]&lt;rowLower[iRow]-10.0*primalTolerance)
733          feasible = false;
734      }
735    }
736    if (feasible) {
737      // new solution
738      memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
739      solutionValue = newSolutionValue;
740      // We have good solution
741      returnCode=1;
742    }
743  }
744     
745  </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. 
746  Branching
747 </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><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="branching"></a>Pseudo Cost Branching</h2></div></div><div></div></div><p>
748
749If the user declares variables as integer but does no more, then CBC will treat them
750as 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
751it 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.
752   The full code is in <tt class="filename">longthin.cpp</tt> located in the CBC Samples directory, see
753  <a href="#moreexamples" title="Chapter 7. &#10;More Samples&#10;">Chapter 7, <i>
754More Samples
755</i></a>.
756</p><p> 
757  The idea is simple for set covering problems.
758  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.
759  The expected cost of going up obviously depends on the cost of the
760  variable. The pseudo costs are choosen to reflect that fact.
761
762  </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">
763   
764  int iColumn;
765  int numberColumns = solver3-&gt;getNumCols();
766  // do pseudo costs
767  CbcObject ** objects = new CbcObject * [numberColumns];
768  // Point to objective
769  const double * objective = model.getObjCoefficients();
770  int numberIntegers=0;
771  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
772    if (solver3-&gt;isInteger(iColumn)) {
773      double cost = objective[iColumn];
774      CbcSimpleIntegerPseudoCost * newObject =
775        new CbcSimpleIntegerPseudoCost(&amp;model,numberIntegers,iColumn,
776                                       2.0*cost,cost);
777      newObject-&gt;setMethod(3);
778      objects[numberIntegers++]= newObject;
779    }
780  }
781  // Now add in objects (they will replace simple integers)
782  model.addObjects(numberIntegers,objects);
783  for (iColumn=0;iColumn&lt;numberIntegers;iColumn++)
784    delete objects[iColumn];
785  delete [] objects;
786     
787  </pre></div><p>
788The code in <a href="#pseudo" title="Example 5.1. CbcSimpleIntegerPseudoCosts">Example 5.1</a> also tries to give more importance to variables with more
789coefficients.  Whether this sort of thing is worthwhile should be the subject of experimentation.
790
791
792</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>
793In 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.
794From DFW there may be several flights the crew could take next - suppose one flight is
795the 9:30 flight from DFW to LAX airport.  A binary branch is that the crew arriving
796at DFW either take the 9:30 flight to LAX or they don't.  This "follow-on" branching does not
797fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW
798constraint into two groups - those with entries in the DFW-LAX constraint and those without
799entries.
800</p><p>
801   The full sample code for follow-on brancing is in <tt class="filename">crew.cpp</tt>
802  located in the CBC Samples directory, see
803  <a href="#moreexamples" title="Chapter 7. &#10;More Samples&#10;">Chapter 7, <i>
804More Samples
805</i></a>).  In this case, the simple integer
806variables 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 indicated the follow-on rules take precedence. Priority 1 is the highest priority.
807
808</p><div class="example"><a id="id2966435"></a><p class="title"><b>Example 5.2. <tt class="classname">CbcFollowOn</tt></b></p><pre class="programlisting">
809   
810  int iColumn;
811  int numberColumns = solver3-&gt;getNumCols();
812  /* We are going to add a single follow-on object but we
813     want to give low priority to existing integers
814     As the default priority is 1000 we don't actually need to give
815     integer priorities but it is here to show how.
816  */
817  // Normal integer priorities
818  int * priority = new int [numberColumns];
819  int numberIntegers=0;
820  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
821    if (solver3-&gt;isInteger(iColumn)) {
822      priority[numberIntegers++]= 100; // low priority
823    }
824  }
825  /* Second parameter is set to true for objects,
826     and false for integers. This indicates integers */
827  model.passInPriorities(priority,false);
828  delete [] priority;
829  /* Add in objects before we can give them a priority.
830     In this case just one object
831     - but it shows the general method
832  */
833  CbcObject ** objects = new CbcObject * [1];
834  objects[0]=new CbcFollowOn(&amp;model);
835  model.addObjects(1,objects);
836  delete objects[0];
837  delete [] objects;
838  // High priority
839  int followPriority=1;
840  model.passInPriorities(&amp;followPriority,true);
841     
842  </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="SolverChap"></a>Chapter 6. 
843  Advance Solver Uses
844</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>
845  CBC uses a generic <tt class="classname">OsiSolverInterface</tt> and its <tt class="function">resolve</tt> capability.
846  This does not give much flexibility so advanced users can inherit from their interface
847  of choice.  This section illustrates how to implement such a 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
848  <a href="#moreexamples" title="Chapter 7. &#10;More Samples&#10;">Chapter 7, <i>
849More Samples
850</i></a>.
851</p><p>
852The 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>.
853  </p><div class="example"><a id="initialSolve"></a><p class="title"><b>Example 6.1. <tt class="function">initialSolve()</tt></b></p><pre class="programlisting">
854   
855  // modelPtr_ is of type ClpSimplex *
856  modelPtr_-&gt;setLogLevel(1); // switch on a bit of printout
857  modelPtr_-&gt;scaling(0); // We don't want scaling for fast0507
858  setBasis(basis_,modelPtr_); // Put basis into ClpSimplex
859  // Do long thin by sprint
860  ClpSolve options;
861  options.setSolveType(ClpSolve::usePrimalorSprint);
862  options.setPresolveType(ClpSolve::presolveOff);
863  options.setSpecialOption(1,3,15); // Do 15 sprint iterations
864  modelPtr_-&gt;initialSolve(options); // solve problem
865  basis_ = getBasis(modelPtr_); // save basis
866  modelPtr_-&gt;setLogLevel(0); // switch off printout
867     
868  </pre></div><p>
869The <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
870a variable was active in a solution.  For the first few times, the normal Dual Simplex is called and
871<tt class="varname">node_</tt> array is updated.
872</p><div class="example"><a id="id2966664"></a><p class="title"><b>Example 6.2. First Few Solves</b></p><pre class="programlisting">
873   
874  if (count_&lt;10) {
875    OsiClpSolverInterface::resolve(); // Normal resolve
876    if (modelPtr_-&gt;status()==0) {
877      count_++; // feasible - save any nonzero or basic
878      const double * solution = modelPtr_-&gt;primalColumnSolution();
879      for (int i=0;i&lt;numberColumns;i++) {
880        if (solution[i]&gt;1.0e-6||modelPtr_-&gt;getStatus(i)==ClpSimplex::basic) {
881          node_[i]=CoinMax(count_,node_[i]);
882          howMany_[i]++;
883        }
884      }
885    } else {
886      printf("infeasible early on\n");
887    }
888  }
889     
890  </pre></div><p>
891After the first few solves, only those variables which took part in a solution in the last so many
892solves are used.  As fast0507 is a set covering problem, any rows which are already covered can be taken out.
893  </p><div class="example"><a id="id2966692"></a><p class="title"><b>Example 6.3. Create Small Problem</b></p><pre class="programlisting">
894   
895    int * whichRow = new int[numberRows]; // Array to say which rows used
896    int * whichColumn = new int [numberColumns]; // Array to say which columns used
897    int i;
898    const double * lower = modelPtr_-&gt;columnLower();
899    const double * upper = modelPtr_-&gt;columnUpper();
900    setBasis(basis_,modelPtr_); // Set basis
901    int nNewCol=0; // Number of columns in small model
902    // Column copy of matrix
903    const double * element = modelPtr_-&gt;matrix()-&gt;getElements();
904    const int * row = modelPtr_-&gt;matrix()-&gt;getIndices();
905    const CoinBigIndex * columnStart = modelPtr_-&gt;matrix()-&gt;getVectorStarts();
906    const int * columnLength = modelPtr_-&gt;matrix()-&gt;getVectorLengths();
907   
908    int * rowActivity = new int[numberRows]; // Number of columns with entries in each row
909    memset(rowActivity,0,numberRows*sizeof(int));
910    int * rowActivity2 = new int[numberRows]; // Lower bound on row activity for each row
911    memset(rowActivity2,0,numberRows*sizeof(int));
912    char * mark = (char *) modelPtr_-&gt;dualColumnSolution(); // Get some space to mark columns
913    memset(mark,0,numberColumns);
914    for (i=0;i&lt;numberColumns;i++) {
915      bool choose = (node_[i]&gt;count_-memory_&amp;&amp;node_[i]&gt;0); // Choose if used recently
916      // Take if used recently or active in some sense
917      if ((choose&amp;&amp;upper[i])
918          ||(modelPtr_-&gt;getStatus(i)!=ClpSimplex::atLowerBound&amp;&amp;
919             modelPtr_-&gt;getStatus(i)!=ClpSimplex::isFixed)
920          ||lower[i]&gt;0.0) {
921        mark[i]=1; // mark as used
922        whichColumn[nNewCol++]=i; // add to list
923        CoinBigIndex j;
924        double value = upper[i];
925        if (value) {
926          for (j=columnStart[i];
927               j&lt;columnStart[i]+columnLength[i];j++) {
928            int iRow=row[j];
929            assert (element[j]==1.0);
930            rowActivity[iRow] ++; // This variable can cover this row
931          }
932          if (lower[i]&gt;0.0) {
933            for (j=columnStart[i];
934                 j&lt;columnStart[i]+columnLength[i];j++) {
935              int iRow=row[j];
936              rowActivity2[iRow] ++; // This row redundant
937            }
938          }
939        }
940      }
941    }
942    int nOK=0; // Use to count rows which can be covered
943    int nNewRow=0; // Use to make list of rows needed
944    for (i=0;i&lt;numberRows;i++) {
945      if (rowActivity[i])
946        nOK++;
947      if (!rowActivity2[i])
948        whichRow[nNewRow++]=i; // not satisfied
949      else
950        modelPtr_-&gt;setRowStatus(i,ClpSimplex::basic); // make slack basic
951    }
952    if (nOK&lt;numberRows) {
953      // The variables we have do not cover rows - see if we can find any that do
954      for (i=0;i&lt;numberColumns;i++) {
955        if (!mark[i]&amp;&amp;upper[i]) {
956          CoinBigIndex j;
957          int good=0;
958          for (j=columnStart[i];
959               j&lt;columnStart[i]+columnLength[i];j++) {
960            int iRow=row[j];
961            if (!rowActivity[iRow]) {
962              rowActivity[iRow] ++;
963              good++;
964            }
965          }
966          if (good) {
967            nOK+=good; // This covers - put in list
968            whichColumn[nNewCol++]=i;
969          }
970        }
971      }
972    }
973    delete [] rowActivity;
974    delete [] rowActivity2;
975    if (nOK&lt;numberRows) {
976      // By inspection the problem is infeasible - no need to solve
977      modelPtr_-&gt;setProblemStatus(1);
978      delete [] whichRow;
979      delete [] whichColumn;
980      printf("infeasible by inspection\n");
981      return;
982    }
983    // Now make up a small model with the right rows and columns
984    ClpSimplex *  temp = new ClpSimplex(modelPtr_,nNewRow,whichRow,nNewCol,whichColumn);
985     
986  </pre></div><p>
987If the variables cover the rows, then the problem is feasible (no cuts are being used). If the rows
988were equality constraints, then this might not be the case. More work would be needed.  After the solution, the reduct costs are checked. If any reduced costs are negative, the code goes back to the full problem and cleans up with Primal Simplex.
989  </p><div class="example"><a id="id2966737"></a><p class="title"><b>Example 6.4. Check Optimal Solution</b></p><pre class="programlisting">
990   
991    temp-&gt;setDualObjectiveLimit(1.0e50); // Switch off dual cutoff as problem is restricted
992    temp-&gt;dual(); // solve
993    double * solution = modelPtr_-&gt;primalColumnSolution(); // put back solution
994    const double * solution2 = temp-&gt;primalColumnSolution();
995    memset(solution,0,numberColumns*sizeof(double));
996    for (i=0;i&lt;nNewCol;i++) {
997      int iColumn = whichColumn[i];
998      solution[iColumn]=solution2[i];
999      modelPtr_-&gt;setStatus(iColumn,temp-&gt;getStatus(i));
1000    }
1001    double * rowSolution = modelPtr_-&gt;primalRowSolution();
1002    const double * rowSolution2 = temp-&gt;primalRowSolution();
1003    double * dual = modelPtr_-&gt;dualRowSolution();
1004    const double * dual2 = temp-&gt;dualRowSolution();
1005    memset(dual,0,numberRows*sizeof(double));
1006    for (i=0;i&lt;nNewRow;i++) {
1007      int iRow=whichRow[i];
1008      modelPtr_-&gt;setRowStatus(iRow,temp-&gt;getRowStatus(i));
1009      rowSolution[iRow]=rowSolution2[i];
1010      dual[iRow]=dual2[i];
1011    }
1012    // See if optimal
1013    double * dj = modelPtr_-&gt;dualColumnSolution();
1014    // get reduced cost for large problem
1015    // this assumes minimization
1016    memcpy(dj,modelPtr_-&gt;objective(),numberColumns*sizeof(double));
1017    modelPtr_-&gt;transposeTimes(-1.0,dual,dj);
1018    modelPtr_-&gt;setObjectiveValue(temp-&gt;objectiveValue());
1019    modelPtr_-&gt;setProblemStatus(0);
1020    int nBad=0;
1021     
1022    for (i=0;i&lt;numberColumns;i++) {
1023      if (modelPtr_-&gt;getStatus(i)==ClpSimplex::atLowerBound
1024          &amp;&amp;upper[i]&gt;lower[i]&amp;&amp;dj[i]&lt;-1.0e-5)
1025        nBad++;
1026    }
1027    // If necessary clean up with primal (and save some statistics)
1028    if (nBad) {
1029      timesBad_++;
1030      modelPtr_-&gt;primal(1);
1031      iterationsBad_ += modelPtr_-&gt;numberIterations();
1032    }
1033     
1034  </pre></div><p>
1035The 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
1036on full problem was less than 20.
1037</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>
1038To give another example - again only for illustrative purposes -- it is possible to do quadratic
1039MIP with CBC.  In this case, we make <tt class="function">resolve</tt> the same as
1040<tt class="function">initialSolve</tt>.
1041   The full code is in <tt class="filename">ClpQuadInterface.hpp</tt> and
1042   <tt class="filename">ClpQuadInterface.cpp</tt> located in the CBC Samples directory, see
1043  <a href="#moreexamples" title="Chapter 7. &#10;More Samples&#10;">Chapter 7, <i>
1044More Samples
1045</i></a>).
1046  </p><div class="example"><a id="id2966802"></a><p class="title"><b>Example 6.5. Solving a Quadratic MIP</b></p><pre class="programlisting">
1047   
1048  // save cutoff
1049  double cutoff = modelPtr_-&gt;dualObjectiveLimit();
1050  modelPtr_-&gt;setDualObjectiveLimit(1.0e50);
1051  modelPtr_-&gt;scaling(0);
1052  modelPtr_-&gt;setLogLevel(0);
1053  // solve with no objective to get feasible solution
1054  setBasis(basis_,modelPtr_);
1055  modelPtr_-&gt;dual();
1056  basis_ = getBasis(modelPtr_);
1057  modelPtr_-&gt;setDualObjectiveLimit(cutoff);
1058  if (modelPtr_-&gt;problemStatus())
1059    return; // problem was infeasible
1060  // Now pass in quadratic objective
1061  ClpObjective * saveObjective  = modelPtr_-&gt;objectiveAsObject();
1062  modelPtr_-&gt;setObjectivePointer(quadraticObjective_);
1063  modelPtr_-&gt;primal();
1064  modelPtr_-&gt;setDualObjectiveLimit(cutoff);
1065  if (modelPtr_-&gt;objectiveValue()&gt;cutoff)
1066    modelPtr_-&gt;setProblemStatus(1);
1067  modelPtr_-&gt;setObjectivePointer(saveObjective);
1068     
1069  </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="moreexamples"></a>Chapter 7. 
1070More Samples
1071</h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#id2968762">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="id2968762"></a>CBC's Samples Directory</h2></div></div><div></div></div><p>
1072The CBC distribution includes a number of <tt class="filename">.cpp</tt> sample files.
1073Users are encouraged to use them as starting points for their own CBC projects.
1074The files can be found in the <tt class="filename">COIN/Cbc/Samples/</tt> directory.
1075For the latest information on compiling and running these samples, please see
1076the file <tt class="filename">COIN/Cbc/Samples/INSTALL</tt>.  Most of them can be built
1077by </p><pre class="programlisting">make DRIVER=name</pre><p> which produces an executable <tt class="filename">testit</tt>.  Below is a list of
1078some of the most useful sample files with a short description for each file.
1079</p><div class="table"><a id="id2969026"></a><p class="title"><b>Table 7.1. Basic Samples</b></p><table summary="Basic Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom">
1080        Source file       
1081        </th><th align="left" valign="bottom">
1082        Description
1083        </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">
1084        This is a CBC "Hello, world" program.  It reads a problem
1085        in MPS file format, and solves the problem using simple branch-and-bound.
1086        </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">
1087        This is designed to be a file that a user could modify to get a useful
1088        driver program for his or her project.  In particular, it demonstrates
1089        the use of CGL's  preprocess functionality.
1090        It uses <tt class="function">CbcBranchUser.cpp</tt>,
1091        <tt class="function">CbcCompareUser.cpp</tt> and
1092        <tt class="function">CbcHeuristicUser.cpp</tt> 
1093        with corresponding <tt class="function">*.hpp</tt> files.
1094        </td></tr></tbody></table></div><div class="table"><a id="id2969203"></a><p class="title"><b>Table 7.2. Advanced Samples</b></p><table summary="Advanced Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom">
1095        Source file       
1096        </th><th align="left" valign="bottom">
1097        Description
1098        </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">
1099        This sample shows the use of advanced branching and a use of priorities.
1100        It uses <tt class="function">CbcCompareUser.cpp</tt>
1101        with corresponding <tt class="function">*.hpp</tt> files.
1102        </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">
1103        This sample shows the advanced use of a solver.  It also has coding for
1104        a greedy heuristic.
1105        The solver is given in <tt class="function">CbcSolver2.hpp</tt> and
1106        <tt class="function">CbcSolver2.cpp</tt>.
1107        The heuristic is given in <tt class="function">CbcHeuristicGreedy.hpp</tt> and
1108        <tt class="function">CbcHeuristicGreedy.cpp</tt>.
1109        It uses <tt class="function">CbcBranchUser.cpp</tt> and
1110        <tt class="function">CbcCompareUser.cpp</tt>
1111        with corresponding <tt class="function">*.hpp</tt> files.
1112        </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">
1113        This solves a quadratic MIP.  It is to show advanced use of a solver.
1114        The solver is given in <tt class="function">ClpQuadInterface.hpp</tt> and
1115        <tt class="function">ClpQuadInterface.cpp</tt>.
1116        It uses <tt class="function">CbcBranchUser.cpp</tt> and
1117        <tt class="function">CbcCompareUser.cpp</tt>
1118        with corresponding <tt class="function">*.hpp</tt> files.
1119        </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">
1120        This artificially creates a Special Ordered Set problem.
1121        </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">
1122        This artificially creates a Lot Sizing problem.
1123        </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 8. 
1124  Messages
1125  </h2></div></div><div></div></div><p>
1126  Messages and codes passed by CBC are listed in the
1127  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.
1128  </p><div class="itemizedlist"><ul type="disc"><li>
1129    <tt class="computeroutput">%s</tt> is a string
1130    </li><li>
1131    <tt class="computeroutput">%d</tt> is an integer
1132    </li><li>
1133    <tt class="computeroutput">%g</tt> or <tt class="computeroutput">%f</tt>
1134    is a floating point value
1135    </li></ul></div><p>
1136
1137  </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>.
1138 </p><div class="itemizedlist"><ul type="disc"><li>
1139    Logging Level 0: Switches off all CBC messages, but one.
1140    </li><li>
1141    Logging Level 1: The default. 
1142    </li><li>
1143    Logging 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.
1144    </li><li>
1145    Logging Level 3: Tremendous amount of information, e.g., multiple messages per node.
1146    </li></ul></div><div class="table"><a id="id2970505"></a><p class="title"><b>Table 8.1. 
1147  CBC Messages Passed At Logging Level 0
1148  </b></p><table summary="&#10;  CBC Messages Passed At Logging Level 0&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1149      Code
1150      </th><th> </th><th align="left">
1151      Text and notes
1152      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1153      3007
1154      </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>
1155
1156      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id2970650"></a><p class="title"><b>Table 8.2. 
1157  CBC Messages Passed At or Above Logging Level 1
1158  </b></p><table summary="&#10;  CBC Messages Passed At or Above Logging Level 1&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1159      Code
1160      </th><th> </th><th align="left">
1161      Text and notes
1162      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1163      1
1164      </td><td> </td><td align="left"><tt class="computeroutput">Search completed - best objective %g, took %d iterations and %d nodes
1165      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1166     
1167      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1168      3
1169      </td><td> </td><td align="left"><tt class="computeroutput">Exiting on maximum nodes
1170      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1171     
1172      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1173      4
1174      </td><td> </td><td align="left"><tt class="computeroutput">
1175      Integer solution of %g found after %d iterations and %d nodes
1176      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1177     
1178      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1179      5
1180      </td><td> </td><td align="left"><tt class="computeroutput">
1181      Partial search - best objective %g (best possible %g), took %d iterations and %d nodes
1182      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1183     
1184      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1185      6
1186      </td><td> </td><td align="left"><tt class="computeroutput">
1187      The LP relaxation is infeasible or too expensive
1188      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1189     
1190      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1191      9
1192      </td><td> </td><td align="left"><tt class="computeroutput">
1193      Objective coefficients multiple of %g
1194      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1195     
1196      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1197      10
1198      </td><td> </td><td align="left"><tt class="computeroutput">
1199      After %d nodes, %d on tree, %g best solution, best possible %g
1200      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1201     
1202      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1203      11
1204      </td><td> </td><td align="left"><tt class="computeroutput">
1205      Exiting as integer gap of %g less than %g or %g%%
1206      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1207           
1208      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1209      12
1210      </td><td> </td><td align="left"><tt class="computeroutput">
1211      Integer solution of %g found by heuristic after %d iterations and %d nodes
1212      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1213     
1214      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1215      13
1216      </td><td> </td><td align="left"><tt class="computeroutput">
1217      At root node, %d cuts changed objective from %g to %g in %d passes
1218      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1219     
1220      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1221      14
1222      </td><td> </td><td align="left"><tt class="computeroutput">
1223      Cut generator %d (%s) - %d row cuts (%d active), %d column cuts %? in %g seconds - new frequency is %d
1224      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1225     
1226      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1227      16
1228      </td><td> </td><td align="left"><tt class="computeroutput">
1229      Integer solution of %g found by strong branching after %d iterations and %d nodes
1230      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1231     
1232      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1233      17
1234      </td><td> </td><td align="left"><tt class="computeroutput">
1235      %d solved, %d variables fixed, %d tightened
1236      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1237     
1238      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1239      18
1240      </td><td> </td><td align="left"><tt class="computeroutput">
1241      After tightenVubs, %d variables fixed, %d tightened
1242      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1243     
1244      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1245      19
1246      </td><td> </td><td align="left"><tt class="computeroutput">
1247      Exiting on maximum solutions
1248      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1249     
1250      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1251      20
1252      </td><td> </td><td align="left"><tt class="computeroutput">
1253      Exiting on maximum time
1254      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1255     
1256      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1257      23
1258      </td><td> </td><td align="left"><tt class="computeroutput">
1259      Cutoff set to %g - equivalent to best solution of %g
1260      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1261     
1262      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1263      24
1264      </td><td> </td><td align="left"><tt class="computeroutput">
1265      Integer solution of %g found by subtree after %d iterations and %d nodes
1266      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1267     
1268      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1269      26
1270      </td><td> </td><td align="left"><tt class="computeroutput">
1271      Setting priorities for objects %d to %d inclusive (out of %d)
1272      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1273     
1274      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1275      3008
1276      </td><td> </td><td align="left"><tt class="computeroutput">
1277      Strong branching is fixing too many variables, too expensively!
1278      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1279     
1280      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id2972014"></a><p class="title"><b>Table 8.3. 
1281  CBC Messages Passed At or Above Logging Level 2
1282  </b></p><table summary="&#10;  CBC Messages Passed At or Above Logging Level 2&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1283      Code
1284      </th><th> </th><th align="left">
1285      Text and notes
1286      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1287      15
1288      </td><td> </td><td align="left"><tt class="computeroutput">
1289      Node %d Obj %g Unsat %d depth %d
1290      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1291     
1292      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1293      21
1294      </td><td> </td><td align="left"><tt class="computeroutput">
1295      On closer inspection node is infeasible
1296      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1297     
1298      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1299      22
1300      </td><td> </td><td align="left"><tt class="computeroutput">
1301      On closer inspection objective value of %g above cutoff of %g
1302      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1303     
1304      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1305      23
1306      </td><td> </td><td align="left"><tt class="computeroutput">
1307      Allowing solution, even though largest row infeasibility is %g
1308      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1309     
1310      </p></td><td class="auto-generated"> </td></tr></tbody></table></div><div class="table"><a id="id2972415"></a><p class="title"><b>Table 8.4. 
1311  CBC Messages Passed At or Above Logging Level 3
1312  </b></p><table summary="&#10;  CBC Messages Passed At or Above Logging Level 3&#10;  " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center">
1313      Code
1314      </th><th> </th><th align="left">
1315      Text and notes
1316      </th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left">
1317      7
1318      </td><td> </td><td align="left"><tt class="computeroutput">
1319      Strong branching on %d (%d), down %g (%d) up %g (%d) value %g
1320      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1321     
1322      </p></td><td class="auto-generated"> </td></tr><tr><td align="left">
1323      25
1324      </td><td> </td><td align="left"><tt class="computeroutput">
1325      %d cleanup iterations before strong branching
1326      </tt></td><td class="auto-generated"> </td></tr><tr><td colspan="2"> </td><td align="left"><p>
1327     
1328      </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="id2974565"></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="id2973929"></a><a id="id2974588"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1329  What is <a href="http://www.coin-or.org/faqs.html#CBC" target="_top">CBC</a>?
1330  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1331  The <a href="http://www.coin-or.org/" target="_top">COIN-OR</a> Branch and Cut code
1332  is designed to be a high quality mixed integer code provided under the terms of the
1333  <a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public License</a>.
1334  CBC is written in C++, and is primarily intended to be used as a callable
1335  library (though a rudimentary stand-alone executable exists).
1336  The first documented release was .90.0  The current release is version .90.0. (JF 04/01/05)
1337  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2974643"></a><a id="id2974646"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1338  What are some of the features of CBC?
1339  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1340  CBC allows the use of any CGL cuts and the use of heuristics and
1341   specialized branching methods. (JF 04/01/05)
1342  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975582"></a><a id="id2975585"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1343  How do I obtain and install CBC?
1344  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1345  Please see the
1346  <a href="http://www.coin-or.org/faqs.html" target="_top">COIN-OR FAQ</a>
1347  for details on how to
1348  <a href="http://www.coin-or.org/faqs.html#ObtainSrcCode" target="_top">obtain</a>
1349  and
1350  <a href="http://www.coin-or.org/faqs.html#BuildCode" target="_top">install</a>
1351  COIN-OR modules. (JF 04/01/05)
1352  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975631"></a><a id="id2975634"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1353  Is CBC reliable?
1354  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1355  CBC has been tested on many problems,
1356  but more testing and improvement is needed before it can get to version 1.0. (JF 04/01/05)
1357  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975657"></a><a id="id2975660"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1358  Is there any documentation for CBC? 
1359  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1360  If you can see this you have the best there is:-)
1361  Also available is a list of
1362  <a href="http://www.coin-or.org/Doxygen/Cbc/" target="_top">CBC class descriptions</a> generated
1363  by <a href="http://www.doxygen.org" target="_top">Doxygen</a>. (JF 04/01/05)
1364  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975698"></a><a id="id2975702"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1365  Is CBC as fast as Cplex or Xpress?
1366  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1367   No. However its design is much more flexible so advanced users
1368   will be able to tailor CBC to their needs. (JF 04/01/05)
1369  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975724"></a><a id="id2975728"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1370  When will version 1.0 of CBC be available? 
1371  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1372  It is expected that version 1.0 will be released in time for the 2005
1373  <a href="http://www.informs.org" target="_top">INFORMS</a> annual meeting. (JF 04/01/05)
1374  </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id2975758"></a><a id="id2975761"></a><b>Q:. </b></td><td align="left" valign="top"><p>
1375  What can the community do to help?
1376  </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p>
1377  People from all around the world are already helping.  There are
1378  probably ten people who do not always post to the discussion mail list but are constantly
1379  "improving" the code by demanding performance or bug fixes or enhancements.  And there
1380  are others posting questions to discussion groups. (JF 04/01/05)
1381  </p><p>
1382  A good start is to join the coin-discuss
1383  <a href="http://www.coin-or.org/mail.html" target="_top">mailing list</a> where CBC is discussed.  Some
1384  other possibilities include:
1385  </p><div class="itemizedlist"><ul type="disc"><li><p>
1386  Comment on the design
1387  </p></li><li><p>
1388  Give feedback on the documentation and FAQs.
1389  </p></li><li><p>
1390  Break the code, or better yet -- mend it.
1391  </p></li><li><p>
1392  Tackle any of the "to-dos" listed in the Doxyen documentation and contribute back to COIN-OR.
1393  </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>
1394There is Doxygen content for CBC available online at
1395<a href="http://www.coin-or.org/Doxygen/Cbc/index.html" target="_top">
1396http://www.coin-or.org/Doxygen/Cbc/index.html</a>.  A local version of the
1397Doxygen content can be generated from the CBC distribution.  To do so, in the
1398directory <tt class="filename">COIN/Cbc</tt>, enter <b class="userinput"><tt>make doc</tt></b>.
1399The Doxygen content will be created in the directory
1400<tt class="filename">COIN/Cbc/Doc/html</tt>.  The same can be done for
1401the COIN core, from the <tt class="filename">COIN/Coin</tt> directory.
1402</p></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="id2974315"></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.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 documenation 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.