Changeset 119


Ignore:
Timestamp:
May 2, 2005 4:37:10 PM (14 years ago)
Author:
rlh
Message:

Revisions for book chapter

Location:
trunk/Docs
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/Docs/cbcmodelclass.xml

    r113 r119  
    22  <chapter id="cbcmodelclass">
    33  <title>
    4   Basic Model Classes
     4   The CBC Model Class
    55  </title>
    66  <section id="hierarchy">
    77  <title>
    8   Hierarchy and list of classes
     8  Overview
    99  </title>
    1010  <para>
     
    2525    </itemizedlist>
    2626  </para>
    27 
    28 <para>
    29 <classname>CbcModel</classname> uses other classes, some of which are virtual and may have multiple instances. Details on the more useful classes used by <classname>CbcModel</classname> will be given later. <!-- where? --> The two tables below list the classes within <classname>CbcModel</classname> that are of most interest and of least interest.
    30 </para>
    31     <table frame="none">
    32   <title>Classes Used by CbcModel - Most Useful</title>
    33     <tgroup cols="3">
    34     <thead>
    35     <row>
    36     <entry>
    37     Class name
    38     </entry>
    39     <entry>
    40     Description
    41     </entry>
    42     <entry>
    43     Notes
    44     </entry>
    45     </row>
    46     </thead>
    47     <tbody>
    48     <row>
    49       <entry align="left" valign="top">
    50       <classname>CbcCompareBase</classname>
    51       </entry>
    52       <entry align="left" valign="top">
    53       Controls which node on tree is selected
    54       </entry>
    55       <entry align="left" valign="top">
    56       The default is <classname>CbcCompareDefault</classname>. Other comparison classes in <filename>CbcCompareActual.hpp</filename> include
    57       <classname>CbcCompareDepth</classname> and <classname>CbcCompareObjective</classname>. It is very easy for user to
    58       experiment with different comparisons.
    59       </entry>
    60     </row>
    61     <row>
    62       <entry align="left" valign="top">
    63       <classname>CbcCutGenerator</classname>
    64       </entry>
    65       <entry align="left" valign="top">
    66       A wrapper for <classname>CglCutGenerator</classname> with additional data to control when the cut generator is used.
    67       </entry>
    68       <entry align="left" valign="top">
    69       Other than knowing how to add a cut generator to <classname>CbcModel</classname>, there is not much the average user needs to know about this class. <!-- what's the default? -->
    70       </entry>
    71     </row>
    72     <row>
    73       <entry align="left" valign="top">
    74       <classname>CbcHeuristic</classname>
    75       </entry>
    76       <entry align="left" valign="top">
    77       Heuristic that attempts to generate valid solutions
    78       </entry>
    79       <entry align="left" valign="top">
    80       Users can get a lot of value out of coding specialized heuristics.  There can be
    81       as many different heuristics as you like. <!-- What's the default? -->
    82       </entry>
    83     </row>
    84     <row>
    85       <entry align="left" valign="top">
    86       <classname>CbcObject</classname>
    87       </entry>
    88       <entry align="left" valign="top">
    89       Defines what it means for a variable to be satisfied.
    90       </entry>
    91       <entry align="left" valign="top">
    92       Virtual class. The branching model used in CBC is based on the idea of an "object". An object has (i) feasible region, (ii) can be evaluated for infeaibility, (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 include simple integer, simple integer with pseudocosts, SOS (type 1 and 2), and lotsizing (see CbcBranch....hpp).
    93       </entry>
    94     </row>
    95     <row>
    96       <entry align="left" valign="top">
    97       <classname>OsiSolverInterface</classname>
    98       </entry>
    99       <entry align="left" valign="top">
    100       Defines the LP solver being used and the LP model. Normally
    101       a pointer to the desired <classname>OsiSolverInteface</classname> is passed to <classname>CbcModel</classname> before branch and cut.
    102       </entry>
    103       <entry align="left" valign="top">
    104       Virtual class. The user instantiates the solver interface of their choice, e.g.,
    105       <classname>OsiClpSolverInterface</classname>.
    106       </entry>
    107     </row>
    108     </tbody>
    109   </tgroup>
    110   </table>
    111 
    112 There is not much in these classes the average user needs to know about.
    113     <table frame="none">
    114   <title>Classes Used by CbcModel - Least Useful</title>
    115     <tgroup cols="3">
    116     <thead>
    117     <row>
    118     <entry>
    119     Class name
    120     </entry>
    121     <entry>
    122     Description
    123     </entry>
    124     <entry>
    125     Notes
    126     </entry>
    127     </row>
    128     </thead>
    129     <tbody>
    130     <row>
    131       <entry align="left" valign="top">
    132       <classname>CbcBranchDecision</classname>
    133       </entry>
    134       <entry align="left" valign="top">
    135       Used in choosing which variable to branch on, however, most of
    136       the work is done by the definitions in <classname>CbcObject</classname>.
    137       </entry>
    138       <entry align="left" valign="top">
    139       Defaults to <classname>CbcBranchDefaultDecision</classname>.
    140       </entry>
    141     </row>
    142     <row>
    143       <entry align="left" valign="top">
    144       <classname>CbcCountRowCut</classname>
    145       </entry>
    146       <entry align="left" valign="top">
    147       Interface to <classname>OsiRowCut</classname>. It counts the usage so cuts can gracefully vanish.
    148       </entry>
    149       <entry align="left" valign="top">
    150       See <classname>OsiRowCut</classname> for more details. <!-- Default? -->
    151       </entry>
    152     </row>
    153     <row>
    154       <entry align="left" valign="top">
    155       <classname>CbcNode</classname>
    156       </entry>
    157       <entry align="left" valign="top">
    158       Controls which variable/entity is selected to be branch on.
    159       </entry>
    160       <entry align="left" valign="top">
    161       Controlled via <classname>CbcModel</classname> parameters.  <!-- Default? -->
    162       </entry>
    163     </row>
    164     <row>
    165       <entry align="left" valign="top">
    166       <classname>CbcNodeInfo</classname>
    167       </entry>
    168       <entry align="left" valign="top">
    169       Contains data on bounds, basis, etc. for one node of the search tree.
    170       </entry>
    171       <entry align="left" valign="top">
    172       Header is located in <filename>CbcNode.hpp</filename>. <!-- Defaults? -->
    173       </entry>
    174     </row>
    175     <row>
    176       <entry align="left" valign="top">
    177       <classname>CbcTree</classname>
    178       </entry>
    179       <entry align="left" valign="top">
    180       Defines how the search tree is stored.
    181       </entry>
    182       <entry align="left" valign="top">
    183       This class can be changed but it is not likely to be modified.<!-- Defaults? -->
    184       </entry>
    185     </row>
    186     <row>
    187       <entry align="left" valign="top">
    188       <classname>CoinMessageHandler</classname>
    189       </entry>
    190       <entry align="left" valign="top">
    191       Deals with message handling
    192       </entry>
    193       <entry align="left" valign="top">
    194       The user can inherit from <classname>CoinMessageHandler</classname> to specialize message handling. 
    195       <!-- Defaults? -->
    196       </entry>
    197     </row>
    198     <row>
    199       <entry align="left" valign="top">
    200       <classname>CoinWarmStartBasis</classname>
    201       </entry>
    202       <entry align="left" valign="top">
    203       Basis representation to be used by solver
    204       </entry>
    205       <entry align="left" valign="top">
    206       <!-- Defaults? -->
    207       </entry>
    208     </row>
    209     </tbody>
    210   </tgroup>
    211   </table>
    21227  </section>
    21328
     
    21732  </title>
    21833  <para>
    219   Below is our first CBC sample program.  It is short enough to present in full.
    220   This code can be found in the CBC Samples directory, see
    221   <xref linkend="moreexamples"/>.  Most of the remaining examples in this Guide
    222   will take the form of small code fragments.
     34  Below is our first CBC sample program.  This program is short enough to present in full.
     35  This code can be found in the CBC Samples directory, <filename>COIN/Cbc/Samples</filename>.
     36  Most of the remaining examples in this Guide will take the form of small code fragments.
    22337  </para>
    224   <example>
     38  <example id="minimum.cpp">
    22539  <title>minimum.cpp</title>
    22640  <programlisting>
     
    26983
    27084  <para>
    271   This sample program creates a <classname>OsiClpSolverInterface</classname> solver interface,
    272   and reads an MPS file. If there are no errors, the program passes the solver to <classname>CbcModel</classname>
    273   which solves it  using the branch-and-bound algorithm.  The part of the program which solves the problem
     85  The sample program <xref linkend="minimum.cpp"/> creates a <classname>OsiClpSolverInterface</classname> solver interface, and reads an MPS file. If there are no errors, the program passes the solver to <classname>CbcModel</classname>
     86  which solves it using the branch-and-bound algorithm.  The part of the program which solves the problem
    27487  is very small (one line!) but before that one line, the LP solver had to be created and populated with data and
    27588  after that one line the results were printed out.
    27689 </para>
    277 
     90</section>
     91
     92<section id="osiAndCbc">
     93<title>
     94The Relationship Between OSI and CBC
     95</title>
    27896<para>
    279   This example illustrates the dependency of CBC on 
    280   the <classname>OsiSolverInterface</classname> methods.
    281   All the OSI methods used in <filename>minimum.cpp</filename> have identical methods in <classname>CbcModel</classname>. <!-- why? -->
    282   But there are many methods in OSI which are not present in CBC. For example, suppose the program produces a lot of out  put so one might add
     97 Example <xref linkend="minimum.cpp"/> illustrates the dependency of CBC on 
     98  the <classname>OsiSolverInterface</classname> class. The constructor of <classname>CbcModel</classname> takes a pointer to an <classname>OsiSolverInterface</classname> (i.e., a solver). The <classname>CbcModel</classname> clones the solver, and uses its own instance of the solver. The <classname>CbcModel</classname>'s solver and the original solver (e.g., <varname>sovler1</varname>) are not in sync unless the user synchronizes them. The user can always access the <classname>CbcModel</classname>'s solver through the <function>model()</function> method.  To synchronize the orignal solver, explicitly refreshing it, e.g., 
     99 <programlisting>
     100  solver1 = model.solver();
     101</programlisting>
     102
     103For convenience, many of the OSI method's to access problem data have identical method names in  <classname>CbcModel</classname>. (It's just more convenient to type <function>model.getNumCols()</function> rather than <function>model.solver()->getNumCols()</function>). While the method names may be identical, sometimes the values they return are not, e.g., <function>getColSolution()</function>. <classname>CbcModel</classname> refreshes its solver at certain logical points. For instance, the OSI method<function>getColSolution()</function> will contain the best solution so far, while the <classname>CbcModel</classname> method may not. In this case, it is safer to use <function>CbcModel::bestSolution()</function>.
     104</para>
     105<para>
     106All the OSI methods used in <filename>minimum.cpp</filename> have equivalent methods in <classname>CbcModel</classname>. But there are some OSI methods which are not present in CBC. For example, if  the program produced a lot of undesired output, one might add the line
    283107</para>
    284108<programlisting>
     
    287111<para>
    288112  <!-- model.solver() returns an OSISolverInterface? -->
    289   to reduce the amount. That improves things a lot but we still get one message per node
    290   so we could add
    291 </para>
    292   <programlisting>
    293    model.setLogLevel(1);
    294   </programlisting>
    295 <para>
    296   The following section gives many of the ways of getting information from the
    297   model or underlying solver.
     113  to reduce the output. There is no <function>model.setHintParam(OsiDoReducePrint,true,OsiHintTry)</function>.
    298114  </para>
    299115  </section>
     116
    300117  <section id="gettingsolution">
    301118  <title>
    302   Getting at the Solution (<classname>CbcModel</classname> methods)
     119  Getting Solution Information Using <classname>CbcModel</classname> Methods
    303120  </title>
    304121  <para>
     
    309126  <function>isAbandoned()</function>. You can also pick up
    310127  <function>int&nbsp;status()</function> which returns 0 if finished,
    311    1 if stopped by user and 2 if difficulties. (status of 0 even if proved
    312    infeasible)
     128   1 if stopped by user and 2 if difficulties. (Note: a status of 0 is returned, even if the model is proved
     129   infeasible.)
    313130  </para>
    314131  <para>
    315   Similarly, we can pick up the solution values.  The OSI methods pick up
    316   the current solution.  This will match the best solution found so far if
    317   called after <function>branchAndBound()</function> and if a solution was found.
     132  Similarly, solution values can be accessed via OSI methods.  The OSI methods pick up
     133  the current solution in the <classname>CBCModel</classname>.  The current solution will match the best solution found so far if called after <function>branchAndBound()</function> and if a solution was found.
    318134  </para>
    319135  <table frame="none">
    320136  <title>
    321   Methods for getting solution information from OSI
     137  Methods for Getting Solution Information from OSI
    322138  </title>
    323139  <tgroup cols="2">
     
    344160      </entry>
    345161      <entry align="left" valign="top">
    346       Outside <classname>CbcModel</classname> will be best solution unless none found.  Safer to use <classname>CbcModel</classname> version,
    347       <function>CbcModel::bestSolution()</function>
     162      The OSI version will return  best solution unless none has been found. It is safer to use <classname>CbcModel</classname> version, <function>CbcModel::bestSolution()</function>
    348163      </entry>
    349164    </row>
     
    406221  </tgroup>
    407222  </table>
    408   <para>
    409   The remainder of this chapter will show more of the basic CBC tasks a user
    410   might wish to perform.
    411   </para>
    412223  </section>
    413224
    414225  <section id="setsandgets">
    415   <title>Useful Set and Get Methods</title>
     226  <title>Useful Set and Get Methods in <classname>CbcModel</classname></title>
    416227  <table frame="none">
    417   <title>Useful Set and Get Methods</title>
     228  <title>Useful Set and Get Methods in <classname>CbcModel</classname></title>
    418229    <tgroup cols="2">
    419230    <thead>
     
    543354      <entry align="left" valign="top">
    544355      <function>const&nbsp;double&nbsp;*&nbsp;getObjCoefficients() const</function><sbr/>
    545     <!--  <function>double&nbsp;*&nbsp;objective()</function> where? -->
    546       </entry>
     356       </entry>
    547357      <entry align="left" valign="top">
    548358      This method return the objective coefficients.
     
    552362      <entry align="left" valign="top">
    553363      <function>const&nbsp;double&nbsp;*&nbsp;getRowLower() const</function><sbr/>
    554     <!--  <function>double&nbsp;*&nbsp;rowLower()</function><sbr/> where? -->
    555       <function>const&nbsp;double&nbsp;*&nbsp;getRowUpper() const</function><sbr/>
    556    <!--  <function>double&nbsp;*&nbsp;rowUpper()</function><sbr/> where? -->
    557       <function>const&nbsp;double&nbsp;*&nbsp;getColLower() const</function><sbr/>
    558    <!--  <function>double&nbsp;*&nbsp;columnLower()</function><sbr/> where? -->
    559       <function>const&nbsp;double&nbsp;*&nbsp;getColUpper() const</function><sbr/>
    560     <!--  <function>double&nbsp;*&nbsp;columnUpper()</function> where? -->
    561       </entry>
     364       <function>const&nbsp;double&nbsp;*&nbsp;getRowUpper() const</function><sbr/>
     365       <function>const&nbsp;double&nbsp;*&nbsp;getColLower() const</function><sbr/>
     366       <function>const&nbsp;double&nbsp;*&nbsp;getColUpper() const</function><sbr/>
     367       </entry>
    562368      <entry align="left" valign="top">
    563369      These methods give lower and upper bounds on row and column activities.
     
    584390    <row>
    585391      <entry align="left" valign="top">
    586       <function>int&nbsp;getNumElements() const</function>
    587 <!--  <function>CoinBigIndex&nbsp;getNumElements() const</function> what? -->
    588 <!--     <footnote> -->
    589 <!--      <para> -->
    590 <!--    <type>CoinBigIndex</type> is a <function>typedef</function> which in -->
    591 <!--    most cases is the same as <type>int</type>. -->
    592 <!--    </para> -->
    593 <!--    </footnote> -->
     392    <function>CoinBigIndex&nbsp;getNumElements() const</function>
     393     <footnote>
     394     <para>
     395        <type>CoinBigIndex</type> is a <function>typedef</function> which in
     396        most cases is the same as <type>int</type>.
     397        </para>
     398    </footnote>
    594399      </entry>
    595400      <entry align="left" valign="top">
     
    613418  <section id="majormethods">
    614419  <title>
    615   Methods which have a Major Impact on Solution Process
     420  Impacting the Solution Process
    616421  </title>
    617422  <para>
    618   These are important methods which will impact search e.g, adding a cut
    619   generator.  The description here may not give all parameters if they are exotic.
    620   More details can be found under the class description column in Table Major Methods.
     423  The methods in <xref linkend="majorMethods"/> can have a major impact on CBC's search.. A brief description is given in the table, along with main parameters. ( The description here may not give all parameters if they are exotic.) The remainder of this documents describes some of the common usages of these methods.
    621424  </para>
    622   <table frame="none">
     425  <table frame="none" id="majorMethods">
    623426  <title>Major Methods</title>
    624427    <tgroup cols="2">
     
    710513  </table>
    711514  </section>
     515
     516<section id="mostAndLeastUsefulClasses">
     517 <title>
     518  Most (and Least) Useful Classes Used by CBC
     519</title>
     520<para>
     521<classname>CbcModel</classname> 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 the classes within <classname>CbcModel</classname> that are of most interest and of least interest.
     522</para>
     523    <table frame="none">
     524  <title>Classes Used by CbcModel - Most Useful</title>
     525    <tgroup cols="3">
     526    <thead>
     527    <row>
     528    <entry>
     529    Class name
     530    </entry>
     531    <entry>
     532    Description
     533    </entry>
     534    <entry>
     535    Notes
     536    </entry>
     537    </row>
     538    </thead>
     539    <tbody>
     540    <row>
     541      <entry align="left" valign="top">
     542      <classname>CbcCompareBase</classname>
     543      </entry>
     544      <entry align="left" valign="top">
     545      Controls which node on tree is selected
     546      </entry>
     547      <entry align="left" valign="top">
     548      The default is <classname>CbcCompareDefault</classname>. Other comparison classes in <filename>CbcCompareActual.hpp</filename> include
     549      <classname>CbcCompareDepth</classname> and <classname>CbcCompareObjective</classname>. It is very easy for user to
     550      experiment with different comparisons.
     551      </entry>
     552    </row>
     553    <row>
     554      <entry align="left" valign="top">
     555      <classname>CbcCutGenerator</classname>
     556      </entry>
     557      <entry align="left" valign="top">
     558      A wrapper for <classname>CglCutGenerator</classname> with additional data to control when the cut generator is used.
     559      </entry>
     560      <entry align="left" valign="top">
     561      Other than knowing how to add a cut generator to <classname>CbcModel</classname>, there is not much the average user needs to know about this class. <!-- what's the default? -->
     562      </entry>
     563    </row>
     564    <row>
     565      <entry align="left" valign="top">
     566      <classname>CbcHeuristic</classname>
     567      </entry>
     568      <entry align="left" valign="top">
     569      Heuristic that attempts to generate valid solutions
     570      </entry>
     571      <entry align="left" valign="top">
     572      Users can get a lot of value out of coding specialized heuristics.  There can be
     573      as many different heuristics as you like. <!-- What's the default? -->
     574      </entry>
     575    </row>
     576    <row>
     577      <entry align="left" valign="top">
     578      <classname>CbcObject</classname>
     579      </entry>
     580      <entry align="left" valign="top">
     581      Defines what it means for a variable to be satisfied.
     582      </entry>
     583      <entry align="left" valign="top">
     584      Virtual class. The branching model used in CBC is based on the idea of an "object". An object has (i) feasible region, (ii) can be evaluated for infeaibility, (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 include simple integer, simple integer with pseudocosts, SOS (type 1 and 2), and lotsizing (see CbcBranch....hpp).
     585      </entry>
     586    </row>
     587    <row>
     588      <entry align="left" valign="top">
     589      <classname>OsiSolverInterface</classname>
     590      </entry>
     591      <entry align="left" valign="top">
     592      Defines the LP solver being used and the LP model. Normally
     593      a pointer to the desired <classname>OsiSolverInteface</classname> is passed to <classname>CbcModel</classname> before branch and cut.
     594      </entry>
     595      <entry align="left" valign="top">
     596      Virtual class. The user instantiates the solver interface of their choice, e.g.,
     597      <classname>OsiClpSolverInterface</classname>.
     598      </entry>
     599    </row>
     600    </tbody>
     601  </tgroup>
     602  </table>
     603
     604There is not much about the classes listed in <xref linkend="least"/> that the average user needs to know about.
     605    <table frame="none" id="least">
     606  <title>Classes Used by CbcModel - Least Useful</title>
     607    <tgroup cols="3">
     608    <thead>
     609    <row>
     610    <entry>
     611    Class name
     612    </entry>
     613    <entry>
     614    Description
     615    </entry>
     616    <entry>
     617    Notes
     618    </entry>
     619    </row>
     620    </thead>
     621    <tbody>
     622    <row>
     623      <entry align="left" valign="top">
     624      <classname>CbcBranchDecision</classname>
     625      </entry>
     626      <entry align="left" valign="top">
     627      Used in choosing which variable to branch on, however, most of
     628      the work is done by the definitions in <classname>CbcObject</classname>.
     629      </entry>
     630      <entry align="left" valign="top">
     631      Defaults to <classname>CbcBranchDefaultDecision</classname>.
     632      </entry>
     633    </row>
     634    <row>
     635      <entry align="left" valign="top">
     636      <classname>CbcCountRowCut</classname>
     637      </entry>
     638      <entry align="left" valign="top">
     639      Interface to <classname>OsiRowCut</classname>. It counts the usage so cuts can gracefully vanish.
     640      </entry>
     641      <entry align="left" valign="top">
     642      See <classname>OsiRowCut</classname> for more details. <!-- Default? -->
     643      </entry>
     644    </row>
     645    <row>
     646      <entry align="left" valign="top">
     647      <classname>CbcNode</classname>
     648      </entry>
     649      <entry align="left" valign="top">
     650      Controls which variable/entity is selected to be branch on.
     651      </entry>
     652      <entry align="left" valign="top">
     653      Controlled via <classname>CbcModel</classname> parameters.  <!-- Default? -->
     654      </entry>
     655    </row>
     656    <row>
     657      <entry align="left" valign="top">
     658      <classname>CbcNodeInfo</classname>
     659      </entry>
     660      <entry align="left" valign="top">
     661      Contains data on bounds, basis, etc. for one node of the search tree.
     662      </entry>
     663      <entry align="left" valign="top">
     664      Header is located in <filename>CbcNode.hpp</filename>. <!-- Defaults? -->
     665      </entry>
     666    </row>
     667    <row>
     668      <entry align="left" valign="top">
     669      <classname>CbcTree</classname>
     670      </entry>
     671      <entry align="left" valign="top">
     672      Defines how the search tree is stored.
     673      </entry>
     674      <entry align="left" valign="top">
     675      This class can be changed but it is not likely to be modified.<!-- Defaults? -->
     676      </entry>
     677    </row>
     678    <row>
     679      <entry align="left" valign="top">
     680      <classname>CoinMessageHandler</classname>
     681      </entry>
     682      <entry align="left" valign="top">
     683      Deals with message handling
     684      </entry>
     685      <entry align="left" valign="top">
     686      The user can inherit from <classname>CoinMessageHandler</classname> to specialize message handling. 
     687      <!-- Defaults? -->
     688      </entry>
     689    </row>
     690    <row>
     691      <entry align="left" valign="top">
     692      <classname>CoinWarmStartBasis</classname>
     693      </entry>
     694      <entry align="left" valign="top">
     695      Basis representation to be used by solver
     696      </entry>
     697      <entry align="left" valign="top">
     698      <!-- Defaults? -->
     699      </entry>
     700    </row>
     701    </tbody>
     702  </tgroup>
     703  </table>
     704</section>
     705
    712706  </chapter>
  • trunk/Docs/cbcuserguide.xml

    r87 r119  
    3636  &cbcmodelclass;
    3737  &otherclasses;
    38   &osibuild;
     38<!--  &osibuild; -->
    3939  &moresamples;
    4040  &messages;
  • trunk/Docs/faqcontent.xml

    r113 r119  
    116116  </para>
    117117  <para>
    118   A good start is to join the CLP
    119   <ulink url="http://www.coin-or.org/mail.html">mailing lists</ulink> where CBC is discussed.  Some
     118  A good start is to join the coin-discuss
     119  <ulink url="http://www.coin-or.org/mail.html">mailing list</ulink> where CBC is discussed.  Some
    120120  other possibilities include:
    121121  </para>
  • trunk/Docs/intro.xml

    r113 r119  
    1212    <footnote>
    1313        <para>
    14         The complete name is "COIN-OR", but for simplicity (and in keeping with the directory and function names) we will simply use "COIN".
     14        The complete acronym is "COIN-OR", but for simplicity (and in keeping with the directory and function names) we will simply use "COIN".
    1515        </para>
    1616      </footnote>
    17 Branch and Cut solver (CBC) is an open-source mixed-integer program (MIP) solver written  in C++.<!-- some intro here to MIP or to open-soure --> CBC is intendend to be used primarily as a callable library to create customized branch-and-cut solvers. A basic, stand-alone <!-- do link **** link linkend="cbcexe"--> executable version is also available.
     17Branch and Cut solver (CBC) is an open-source mixed-integer program (MIP) solver written  in C++.<!-- some intro here to MIP or to open-soure --> CBC is intendend to be used primarily as a callable library to create customized branch-and-cut solvers. A basic, stand-alone <!-- do link **** link linkend="cbcexe"--> executable version is also available. CBC is an active open-source project led by John Forrest at www.coin-or.org.
    1818 </para>
    1919 </section>
     
    3535  <para>
    3636<!-- dependencies -->
    37 CBC relies on many other parts of the COIN repository. CBC relies the COIN Open Solver Inteface (OSI) to communicate with the LP solver. CBC needs an LP solver and 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 CoinFactorization. This document assumes basic familiarity with OSI and CGL.
     37CBC relies other parts of the COIN repository. CBC relies the COIN Open Solver Inteface (OSI) to communicate with the LP solver. CBC needs an LP solver and 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 CoinFactorization. This document assumes basic familiarity with OSI and CGL.
    3838</para>
    3939<para>
     
    4545<section>
    4646<title>
    47 Overview
     47Branch-and-Cut Overview
    4848</title>
    4949  <para>
    50   Before examining CBC in more detail, we tersely describe the basic branch-and-cut algorithm (which should really be called branch-and-cut-and-bound) and show the major C++ class(es) in CBC related to each step. The CBC classes, labeled (A) through (F), are described in Table 1.1.
     50  Before examining CBC in more detail, we tersely describe the basic branch-and-cut algorithm (which should really be called branch-and-cut-and-bound) and show the major C++ class(es) in CBC related to each step. The CBC classes, labeled (A) through (F), are described in <xref linkend="assClasses"/>.
    5151 </para>
    5252
     
    8282 </para>
    8383 <para>     
    84 This 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 just used in step 1, the method is called a cut-and-branch algorithm.)
     84This 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 just used in Step 1, the method is called a cut-and-branch algorithm.)
    8585 
    8686  <!-- rlh: this explaination is for people who already know b&c -->
    8787  </para>
    88     <table frame="none">
    89   <title>Associated classes</title>
     88  <table frame="none" id="assClasses">
     89  <title>Associated Classes</title>
    9090    <tgroup cols="3">
    9191    <thead>
     
    197197  </section>
    198198
    199 
    200 
    201199  </chapter>
  • trunk/Docs/otherclasses.xml

    r113 r119  
    22  <chapter id="otherclasses">
    33  <title>
    4   Other Classes and Examples
     4  Selecting a Node in the Search Tree
    55  </title>
    66  <section id="comparison">
     
    99  The order in which the nodes of the tree are explored is not predetermined and can be influenced by the user.
    1010  CBC provides a abstract base class <classname>CbcCompareBase</classname>
    11   and several instances which are described in Table Compare Classes Provided.
    12   </para>
    13     <table frame="none">
     11  and several instances which are described in <xref linkend="compareTable"/>.
     12  </para>
     13    <table frame="none" id="compareTable">
    1414  <title>Compare Classes Provided</title>
    1515    <tgroup cols="2">
     
    256256  </example>
    257257  </section>
     258</chapter>
     259<chapter id="hueristicChap">
     260  <title>
     261  Using Hueristics in CBC
     262  </title>
    258263  <section id="heuristics">
    259264  <title>CbcHeuristic - Heuristic Methods</title>
     
    453458  </example>
    454459  </section>
     460</chapter>
     461
     462<chapter id="branchChapter">
     463  <title>
     464  Branching
     465 </title>
    455466  <section id="branching">
    456467  <title>Branching</title>
     
    555566  </example>
    556567  </section>
     568</chapter>
     569<chapter id="SolverChap">
     570<title>
     571Advance Use of Solver
     572</title>
    557573  <section id="solver">
    558   <title>Advanced use of solver</title>
    559   <para>
    560   Coin Branch and Cut uses a generic OsiSolverInterface and its <function>resolve</function> capability.
     574  <title>Advanced Use of Solver</title>
     575  <para>
     576  Coin Branch and Cut uses a generic <classname>OsiSolverInterface</classname> and its <function>resolve</function> capability.
    561577  This does not give much flexibility so advanced users can inherit from the interface
    562578  of choice.  This describes such a solver for a long thin problem e.g. fast0507 again.
     
    568584  <xref linkend="moreexamples"/>).
    569585  <function>initialSolve</function> is called a few times so although we will not gain much
    570   this is a simpler place to start.  The example derives from OsiClpSolverInterface and the code
     586  this is a simpler place to start.  The example derives from <classname>OsiClpSolverInterface</classname> and the code
    571587  is:
    572588  </para>
     
    592608<para>
    593609The <function>resolve</function> method is more complicated.  The main pieces of data are
    594 a counter count_ which is incremented each solve and an int array node_ which stores the last time
     610a counter <varname>count_</varname>which is incremented each solve and an int array <varname>node_</varname> which stores the last time
    595611a variable was active in a solution.  For the first few times normal dual is called and
    596 node_ array is updated.
     612<varname>node_</varname> array is updated.
    597613</para>
    598614  <example>
     
    721737  </example>
    722738<para>
    723 If the variables cover the rows then we know that the problem is feasible (We are not using
     739If the variables cover the rows then we know that the problem is feasible (we are not using
    724740cuts).  If the rows
    725741were E rows then this might not be the case and we would have to do more work.  When we have solved
     
    777793  </example>
    778794<para>
    779 We then update node_ array as for the first few solves.  To give some idea of the effect of this
     795We then update <varname>node_</varname> array as for the first few solves.  To give some idea of the effect of this
    780796tactic fast0507 has 63,009 variables and the small problem never has more than 4,000 variables.
    781797In just over ten percent of solves did we have to resolve and then the average number of iterations
  • trunk/Docs/revhist.xml

    r113 r119  
    77  <date>May 2, 2005</date>
    88  <authorinitials>RLH</authorinitials>
    9   <revremark>Book chapter for CBC Tutorial at INFORMS annual meeting 2005. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.</revremark>
     9  <revremark>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.</revremark>
    1010</revision>
    1111<revision>
     
    1313  <date>April 1, 2005</date>
    1414  <authorinitials>JF</authorinitials>
    15   <revremark>First draft.</revremark>
     15  <revremark>First draft. The CBC documenation uses the DocBook CLP documentation created by David de la Nuez.</revremark>
    1616</revision>
    1717</revhistory>
Note: See TracChangeset for help on using the changeset viewer.