Changeset 120


Ignore:
Timestamp:
May 3, 2005 9:03:29 AM (14 years ago)
Author:
rlh
Message:

Rennovated Cbc user guide for INFORMS Tutorial book chapter

Location:
trunk/Docs
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Docs/cbcmodelclass.xml

    r119 r120  
    99  </title>
    1010  <para>
    11   The class that controls CBC is <classname>CbcModel</classname>.  This class is where most
    12   of the parameter setting is done. The absolute minimum number of actions for <classname>CbcModel</classname> is two:
    13 
     11  The main class in CBC is <classname>CbcModel</classname>.  The <classname>CbcModel</classname> class is where most
     12  of the parameter setting is done. The absolute minimum number of actions taken with <classname>CbcModel</classname> is two,
    1413    <itemizedlist>
    1514    <listitem>
     
    2928  <section id="firstexample">
    3029  <title>
    31   First Example
     30  Simple Branch-and-Bound Example
    3231  </title>
    3332  <para>
    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.
     33  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.
     34  The complete code for all the examples in this Guide can be found in the CBC Samples directory, <filename>COIN/Cbc/Samples</filename>.
     35
    3736  </para>
    3837  <example id="minimum.cpp">
     
    5756  assert(numMpsReadErrors==0);
    5857
    59   // Pass the solver (with the problem data) to CbcModel
     58  // Pass the solver with the problem to be solved to CbcModel
    6059  CbcModel model(solver1);
    6160
     
    6362  model.branchAndBound();
    6463
    65   /* Print the solution.  CbcModel clones solver so we
     64  /* Print the solution.  CbcModel clones the solver so we
    6665     need to get current copy from the CbcModel */
    6766  int numberColumns = model.solver()->getNumCols();
     
    7978  </programlisting>
    8079  </example>
    81   <!-- Clone comment  needs more explaination. What info is safe? When do you need to do a refresh?? -->
     80  <!-- Clone comment  needs more explanation. What info is safe? When do you need to do a refresh?? -->
    8281  <!-- printf vs cout  -->
    8382
    8483  <para>
    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
    87   is very small (one line!) but before that one line, the LP solver had to be created and populated with data and
    88   after that one line the results were printed out.
     84  The program in <xref linkend="minimum.cpp"/> creates a <classname>OsiClpSolverInterface</classname> solver interface (i.e., <varname>solver1</varname>), and reads an MPS file. If there are no errors, the program passes the problem to <classname>CbcModel</classname> 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., <varname>solver1</varname>) had to be created and populated with the problem. After that one line, the results were printed out.
    8985 </para>
    9086</section>
     
    9591</title>
    9692<para>
    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., 
     93The program in <xref linkend="minimum.cpp"/> illustrates the dependency of CBC on 
     94  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>solver1</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 two solvers, explicitly refreshing the original, e.g., 
    9995 <programlisting>
    10096  solver1 = model.solver();
    10197</programlisting>
    102 
    103 For 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>.
     98<classname>CbcModel</classname>'s method <function>solve()</function> returns a pointer to CBC's cloned solver.
     99</para>
     100
     101<para>
     102For convenience, many of the OSI methods 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>). The <classname>CbcModel</classname> refreshes its solver at certain logical points during the algorithm. At these points, the information from the <classname>CbcModel</classname> <varname>model</varname> will match the information from the <function>model.solver()</function>. Elsewhere, the information may vary. 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>.
    104103</para>
    105104<para>
    106 All 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
     105While all the OSI methods used in <filename>minimum.cpp</filename> have equivalent methods in <classname>CbcModel</classname>, there are some OSI methods which do not. For example, if  the program produced a lot of undesired output, one might add the line
    107106</para>
    108107<programlisting>
     
    111110<para>
    112111  <!-- model.solver() returns an OSISolverInterface? -->
    113   to reduce the output. There is no <function>model.setHintParam(OsiDoReducePrint,true,OsiHintTry)</function>.
     112  to reduce the output. There is no <function>setHintParam()</function> method in <classname>CbcModel</classname>.
    114113  </para>
    115114  </section>
     
    117116  <section id="gettingsolution">
    118117  <title>
    119   Getting Solution Information Using <classname>CbcModel</classname> Methods
     118  Getting Solution Information
    120119  </title>
    121120  <para>
    122   The OSI way to check for optimality is to call <function>model.isProvenOptimal()</function>.  Also
     121  Optimality can be checked through a call to <function>model.isProvenOptimal()</function>.  Also
    123122  available are <function>isProvenInfeasible()</function>,
    124123  <function>isSolutionLimitReached()</function>,
    125124  <function>isNodeLimitReached()</function> or the feared
    126   <function>isAbandoned()</function>. You can also pick up
    127   <function>int&nbsp;status()</function> which returns 0 if finished,
    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.)
     125  <function>isAbandoned()</function>. There is also
     126  <function>int&nbsp;status()</function> 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.
    130127  </para>
    131128  <para>
    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.
     129  In addition to these <classname>CbcModel</classname> methods, solution values can be accessed via OSI methods.  The OSI methods pick up 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 a solution was found.
    134130  </para>
    135131  <table frame="none">
     
    160156      </entry>
    161157      <entry align="left" valign="top">
    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>
     158      The OSI method will return the best solution found thus far, unless none has been found. It is safer to use <classname>CbcModel</classname> version, <function>CbcModel::bestSolution()</function>
    163159      </entry>
    164160    </row>
     
    204200      </entry>
    205201      <entry align="left" valign="top">
    206       Identical <classname>CbcModel</classname> version available, <function>CbcModel::getNumRows()</function>, but note that the number of rows may change due to cuts.
     202      Identical <classname>CbcModel</classname> version available, <function>CbcModel::getNumRows()</function>. Note: the number of rows can change due to cuts.
    207203      </entry>
    208204    </row>
     
    224220
    225221  <section id="setsandgets">
    226   <title>Useful Set and Get Methods in <classname>CbcModel</classname></title>
    227   <table frame="none">
     222  <title>
     223   Useful Set and Get Methods in <classname>CbcModel</classname>
     224  </title>
     225<para>
     226Most of the parameter setting in CBC is done through <classname>CbcModel</classname> methods. The most commonly used set and get methods are listed in <xref linkend="setGet"/>.
     227</para>
     228  <table frame="none" id="setGet">
    228229  <title>Useful Set and Get Methods in <classname>CbcModel</classname></title>
    229230    <tgroup cols="2">
     
    250251      </entry>
    251252      <entry align="left" valign="top">
    252       These methods tell CBC to stop after a given number of nodes or
    253       seconds or solutions (and returns these values).
     253      These set methods tell CBC to stop after a given number of nodes,
     254      seconds, or solutions is reached. The get methods return the corresponding values.
    254255      </entry>
    255256    </row>
     
    260261      </entry>
    261262      <entry align="left" valign="top">
    262       An integer variable
    263       is deemed to be at an integral value if it is no further than this tolerance
    264       away.
     263      An integer variable is deemed to be at an integral value if it is no further than this <parameter>value</parameter> (tolerance) away.
    265264      </entry>
    266265    </row>
     
    276275      <entry align="left" valign="top">
    277276      <classname>CbcModel</classname> returns if the gap between the best known solution and the best
    278       possible solution is less than this (or as a percentage or fraction).
     277      possible solution is less than this <parameter>value</parameter>, or as a percentage, or a fraction.
    279278      </entry>
    280279    </row>
     
    282281      <entry align="left" valign="top">
    283282      <function>void&nbsp;setNumberStrong(double value) </function><sbr/>
    284       <function>int&nbsp;numberStrong() const </function>
    285       </entry>
    286       <entry align="left" valign="top">
    287       Get or set the maximum number of candidates at a node to
     283      <function>int&nbsp;numberStrong() const </function> <!-- should be a "get" -->
     284      </entry>
     285      <entry align="left" valign="top">
     286      These methods set or get the maximum number of candidates at a node to
    288287      be evaluated for strong branching.
    289288      </entry>
     
    296295      <entry align="left" valign="top">
    297296      Controls the number of nodes evaluated between status prints.
    298       Print frequency has very slight overhead if small.
     297      Print frequency has a very slight overhead, if <parameter>value</parameter> is small.
    299298      </entry>
    300299    </row>
     
    304303      </entry>
    305304      <entry align="left" valign="top">
    306       Returns number of nodes search took
     305      Returns number of nodes evaluated in the search.
    307306      </entry>
    308307    </row>
     
    312311      </entry>
    313312      <entry align="left" valign="top">
    314       Returns number of rows at continuous
     313      Returns number of rows at continuous <!-- rlh: huh? -->
    315314      </entry>
    316315    </row>
     
    321320      </entry>
    322321      <entry align="left" valign="top">
    323       Returns number of integers and an array giving which ones
     322      Returns number of integer variables and an array specifying them.
    324323      </entry>
    325324    </row>
     
    331330      </entry>
    332331      <entry align="left" valign="top">
    333       Returns information on a variable.  You can use OSI methods
    334       to set these attributes (before handing to <classname>CbcModel</classname>)
     332      Returns information on variable <parameter>colIndex</parameter>. OSI methods
     333      can be used to set these attributes (before handing the model to <classname>CbcModel</classname>).
    335334      </entry>
    336335    </row>
     
    367366       </entry>
    368367      <entry align="left" valign="top">
    369       These methods give lower and upper bounds on row and column activities.
     368      These methods return the lower and upper bounds on row and column activities.
    370369      </entry>
    371370    </row>
     
    375374      </entry>
    376375      <entry align="left" valign="top">
    377       This method returns a pointer to a row copy of matrix
     376      This method returns a pointer to a row copy of matrix stored as a
    378377      <classname>CoinPackedMatrix</classname> which can be further examined.
    379378      </entry>
     
    384383      </entry>
    385384      <entry align="left" valign="top">
    386       This method returns a pointer to a column copy of matrix
     385      This method returns a pointer to a column copy of matrix stored as a
    387386      <classname>CoinPackedMatrix</classname> which can be further examined.
    388387      </entry>
     
    399398      </entry>
    400399      <entry align="left" valign="top">
    401       Returns the number of elements in the problem matrix.
     400      Returns the number of nonzero elements in the problem matrix.
    402401      </entry>
    403402    </row>
     
    420419  Impacting the Solution Process
    421420  </title>
    422   <para>
    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.
    424   </para>
    425   <table frame="none" id="majorMethods">
    426   <title>Major Methods</title>
    427     <tgroup cols="2">
    428     <thead>
    429     <row>
    430     <entry>
    431     Method(s)
    432     </entry>
    433     <entry>
    434     Description
    435     </entry>
    436     </row>
    437     </thead>
    438     <tbody>
    439     <row>
    440       <entry align="left" valign="top">
    441       <function>passInPriorities(const int * priorities, bool ifNotSimpleIntegers,
    442                         int defaultValue=1000)</function>
    443       </entry>
    444       <entry align="left" valign="top">
    445       Normally this is a list of priorities (1 being highest) and the other
    446       <parameter>ifNotSimpleIntegers</parameter> being false which set priorities for all integer
    447       variables.  If two variables are unsatisfied and one has a higher priority
    448       then it is always preferred whatever its value.  This can be very powerful
    449       but also see PseudoCosts in <classname>CbcObject</classname> discussion.
    450       </entry>
    451     </row>
    452     <row>
    453       <entry align="left" valign="top">
    454       <function>addCutGenerator(CglCutGenerator *,int howOften, const char * name)</function>
    455       </entry>
    456       <entry align="left" valign="top">
    457       This is used to add a cut generator to <classname>CbcModel</classname>.  Any cut generator in CGL can be used. If <parameter>howOften</parameter> &gt; 0 then <parameter>name</parameter> will be called at root node and again every <parameter>howOften</parameter> nodes. There is an option to override and to call <parameter>name</parameter> depth 0,k,2k, etc.  If <parameter>howOften</parameter> = -1 then the code determines how effective <parameter>name</parameter>is at root node and dynamically sets <parameter>howOften</parameter>. If <parameter>howOften</parameter> = -99 then <parameter>name></parameter> is just used at root node.
    458       There is also a redundant <parameter>howOften</parameter> = -100 setting which switches <parameter>name</parameter> off. This parameter setting is useful for testing.  For usage see <filename>sample2.cpp</filename> in the <filename>COIN/Cbc/Samples</filename> directory <xref linkend="moreexamples"/> which uses the most common cut generators.
    459       </entry>
    460     </row>
    461     <row>
    462       <entry align="left" valign="top">
    463       <function>addHeuristic(CbcHeuristic *)</function>
    464       </entry>
    465       <entry align="left" valign="top">
    466       This adds one heuristic to <classname>CbcModel</classname>.See the section on <classname>CbcHeuristic</classname>  to obtain
    467       a list of available heuristics and a guide as to building new ones.
    468       </entry>
    469     </row>
    470     <row>
    471       <entry align="left" valign="top">
    472       <function>addObjects(int&nbsp;number,CbcObject&nbsp;**&nbsp;objects) </function>
    473       </entry>
    474       <entry align="left" valign="top">
    475       This adds members of the base class <classname>CbcObject</classname> to <classname>CbcModel</classname>.  See the section
    476       on <classname>CbcObject</classname> for detailed nformation.  The <parameter>objects</parameter> are cloned by the code so the
    477       user should delete them after the call to <function>addObjects</function>.  There are two
    478       main cases.  The first is when the originally created objects are left and
    479       new ones added (maybe with a higher priority);  this might be used when
    480       simple integer objects exist and Special Ordered Sets of type 1 are going
    481       to be added, which while not necessary will give extra power in branching.
    482       The second case is when the old ones are being deleted. 
    483       For usage see <filename>sos.cpp</filename> in the <filename>COIN/Cbc/Samples</filename> directory <xref linkend="moreexamples"/>.
    484       </entry>
    485     </row>
    486     <row>
    487       <entry align="left" valign="top">
    488       <function>CglPreProcess::preProcess(OsiSolverInterface &amp;)</function>
    489       </entry>
    490       <entry align="left" valign="top">
    491       This is not really part of CBC and can be used by other mixed integer
    492       solvers but it can be a useful tool.  It tries to fix variables and
    493       strengthen coefficients and also do a normal presolve.  Owing to the
    494       odd nature of integer programming it may not always reduce the time
    495       taken but is definitely worth trying.  For an example of using
    496       <function>CglPreProcess()</function> (and <function>CglPostProcess()</function>) see <filename>sample2.cpp</filename> in the CBC Samples
    497       directory <xref linkend="moreexamples"/>.
    498       </entry>
    499     </row>
    500     <row>
    501       <entry align="left" valign="top">
    502       <function>setNodeComparison(CbcCompareBase&nbsp;*)</function>
    503       </entry>
    504       <entry align="left" valign="top">
    505        This is used to invoke a non-default node comparisons
    506        in determining the next node on tree to explore. The order a tree is explored
    507        can make a large difference in runtime. Specialized comparisons are easy to implement.
    508        See the section on <classname>CbcCompare</classname>.
    509       </entry>
    510     </row>
    511     </tbody>
    512   </tgroup>
    513   </table>
    514   </section>
    515 
    516 <section id="mostAndLeastUsefulClasses">
    517  <title>
    518   Most (and Least) Useful Classes Used by CBC
    519 </title>
    520421<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.
     422<classname>CbcModel</classname> 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:
     423    <itemizedlist>
     424    <listitem>
     425    <simpara>
     426     selecting the next node to consider in the search tree,
     427    </simpara>
     428    </listitem>
     429    <listitem>
     430    <simpara>
     431    determining which variable to branch on,
     432    </simpara>
     433    </listitem>
     434   <listitem>
     435    <simpara>
     436    using heuristics to generate MIP-feasible solutions quickly,
     437    </simpara>
     438    </listitem>
     439   <listitem>
     440    <simpara>
     441    including cut generation when solving the LP-relaxations, and
     442    </simpara>
     443    </listitem>
     444  <listitem>
     445    <simpara>
     446    invoking customized subproblem solvers.
     447    </simpara>
     448    </listitem>
     449    </itemizedlist>
     450
     451
     452To enable this flexibility,  <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 in alphabetical order the classes used by <classname>CbcModel</classname> that are of most interest and of least interest.
    522453</para>
    523454    <table frame="none">
     
    543474      </entry>
    544475      <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.
     476      Controls which node on the tree is selected.
     477      </entry>
     478      <entry align="left" valign="top">
     479      The default is <classname>CbcCompareDefault</classname>. Other comparison classes in <filename>CbcCompareActual.hpp</filename> include <classname>CbcCompareDepth</classname> and <classname>CbcCompareObjective</classname>. Experimenting with these classes and creating new compare classes is easy.
    551480      </entry>
    552481    </row>
     
    556485      </entry>
    557486      <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? -->
     487      A wrapper for <classname>CglCutGenerator</classname> with additional data to control when the cut generator is invoked during the tree search.
     488      </entry>
     489      <entry align="left" valign="top">
     490      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. However, sophisticated users can implement their own cut generators. <!-- what's the default? -->
    562491      </entry>
    563492    </row>
     
    567496      </entry>
    568497      <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? -->
     498      Heuristic that attempts to generate valid MIP-solutions leading to good upper bounds.
     499      </entry>
     500      <entry align="left" valign="top">
     501      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. <!-- What's the default? -->
    574502      </entry>
    575503    </row>
     
    579507      </entry>
    580508      <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).
     509      Defines what it means for a variable to be satisfied. Used in branching.
     510      </entry>
     511      <entry align="left" valign="top">
     512      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 <classname>CbcSimpleInteger</classname>, <classname>CbcSimpleIntegerPseudoCosts</classname>, <classname>CbcClique</classname>, <classname>CbcSOS</classname> (type 1 and 2), <classname>CbcFollowOn</classname>, and <classname>CbcLotsize</classname>.
    585513      </entry>
    586514    </row>
     
    601529  </tgroup>
    602530  </table>
    603 
     531<para>
    604532There is not much about the classes listed in <xref linkend="least"/> that the average user needs to know about.
     533</para>
    605534    <table frame="none" id="least">
    606535  <title>Classes Used by CbcModel - Least Useful</title>
     
    651580      </entry>
    652581      <entry align="left" valign="top">
    653       Controlled via <classname>CbcModel</classname> parameters. <!-- Default? -->
     582      Controlled via <classname>CbcModel</classname> parameters. Information from <classname>CbcNode</classname> can be useful in creating customized node selection rules. <!-- Default? -->
    654583      </entry>
    655584    </row>
  • trunk/Docs/intro.xml

    r119 r120  
    1212    <footnote>
    1313        <para>
    14         The complete acronym 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" 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".
    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. CBC is an active open-source project led by John Forrest at www.coin-or.org.
     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-source --> CBC is intended 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 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.
    38 </para>
    39 <para>
    40 Technically speaking, CBC acesses the solver (and sometime the model and data it contains) through an OSISolverInterface. For the sake of simplicity, we will refer to the <classname>OsiSolverInterface</classname> as "the solver" in this document, rather than "the standard appplication programming interface to the solver". We hope any confusion caused by bluring this distinction will be mitigated by the shorter sentences. 
     37CBC 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 <classname>CoinFactorization</classname>. This document assumes basic familiarity with OSI and CGL.
     38</para>
     39<para>
     40Technically speaking, CBC assesses the solver (and sometime the model and data it contains) through an <classname>OSISolverInterface</classname>. For the sake of simplicity, we will refer to the <classname>OsiSolverInterface</classname> 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. 
    4141 <!-- need a link to OSI and CGL documentation. Shoot, need OSI and CGL documentation! -->
    4242 </para>
     43<para>
     44In summary, readers should have the following prerequisites:
     45   <itemizedlist>
     46    <listitem>
     47    <simpara>
     48    C++ knowledge,
     49    </simpara>
     50    </listitem>
     51    <listitem>
     52    <simpara>
     53    LP and MIP fundamentals, and   
     54    </simpara>
     55    </listitem>
     56    <listitem>
     57    <simpara>
     58    OSI familiarity.
     59    </simpara>
     60    </listitem>
     61    </itemizedlist>
     62</para>
     63<para>
     64Unless otherwise stated, we will assume the problem being optimized is a minimization problem. The terms "model" and "problem" are used synonymously.
     65</para>
    4366 </section>
    4467
     
    4871</title>
    4972  <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 <xref linkend="assClasses"/>.
    51  </para>
    52 
    53   <para>
    54 Step 1. (Bound) Say we are given a MIP model to minimize where some variables must take on integer values (e.g., 0, 1, or 2). Relax the integrality requirement (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. Stop.   
     73  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 <xref linkend="assClasses"/>.
     74 </para>
     75
     76  <para>
     77Step 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.   
    5578 </para>
    5679 <para> 
    57 Step 2. (Branch) Otherwise, choose one non-integral variable (e.g., with value 1.3) (A)(B) and branch.
    58 Create two nodes, one a linear model with the branching variable having an upper bound of 1.0, and the other a linear model withe branching variable having a lower bound of 2.0. Add the two nodes to the search tree.
     80Step 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.
    5981 </para>
    6082 <para>
     
    6890</para>
    6991<para>
    70    Step 5. (Bound) Interregate optimal LP solution.
    71            If we can't prune the node by  the following,
    72                   (i)  LP is infeasible, prune the node.
    73                   (ii) Else, the optimal LP solution value exceeds the current upper bound, prune the node. 
    74                   (ii) Else, the optimal LP solution does not exceed the current upper bound and is feasible to the MIP.                       Update the upper bound, and the best known MIP solution, and  prune the node by optimality.           then branch.
    75 </para>
    76 <para>
    77    Step 6. (Branch) Choose one non-integral variable to *branch* on (A)(B).
    78            Create two nodes and add them to the search tree.
    79 </para>
    80 <para>
     92   Step 5. (Bound) Interrogate the optimal LP solution, and try to prune the node by one of the following.
     93   <itemizedlist>
     94    <listitem>
     95    <simpara>
     96    LP is infeasible, prune the node.
     97    </simpara>
     98    </listitem>
     99    <listitem>
     100    <simpara>
     101    Else, the optimal LP solution value of the node exceeds the current upper bound, prune the node. 
     102    </simpara>
     103    </listitem>
     104    <listitem>
     105    <simpara>
     106    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.         
     107    </simpara>
     108    </listitem>
     109    </itemizedlist> 
     110</para>
     111<para>
     112   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.
    81113}
    82114 </para>
    83115 <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.)
     116This 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.)
    85117 
    86118  <!-- rlh: this explaination is for people who already know b&c -->
     
    113145      These classes define the nature of MIP's discontinuity.  The simplest discontinuity
    114146      is a variable which must take an integral value. Other types of discontinuities
    115       will be described later (e.g., lotsizing variables).
     147      exist, e.g., lot-sizing variables.
    116148      <!--rlh: why "...."? Currently 4: CbcBranchActual.cpp, CbcBranchBase.cpp CbcBranchCut.cpp, CbcBranchLotsizes.cpp-->
    117149      </entry>
  • trunk/Docs/moresamples.xml

    r113 r120  
    3535        <entry align="left" valign="top">
    3636        This is a CBC &quot;Hello, world&quot; program.  It reads a problem
    37         in MPS file format, and solves the problem.
     37        in MPS file format, and solves the problem using simple branch-and-bound.
    3838        </entry>
    3939      </row>
     
    4545        This is designed to be a file that a user could modify to get a useful
    4646        driver program for his or her project.  In particular, it demonstrates
    47         the use of Cgl's  preprocess functionality.
     47        the use of CGL's  preprocess functionality.
    4848        It uses <function>CbcBranchUser.cpp</function>,
    4949        <function>CbcCompareUser.cpp</function> and
     
    100100        </entry>
    101101        <entry align="left" valign="top">
    102         This solves a quadratic mip.  It is to show advanced use of a solver.
     102        This solves a quadratic MIP.  It is to show advanced use of a solver.
    103103        The solver is given in <function>ClpQuadInterface.hpp</function> and
    104104        <function>ClpQuadInterface.cpp</function>.
     
    113113        </entry>
    114114        <entry align="left" valign="top">
    115         This artificially creates a Special Ordered set problem.
     115        This artificially creates a Special Ordered Set problem.
    116116        </entry>
    117117      </row>
     
    121121        </entry>
    122122        <entry align="left" valign="top">
    123         This artificially creates a lot sizing problem.
     123        This artificially creates a Lot Sizing problem.
    124124        </entry>
    125125      </row>
  • trunk/Docs/otherclasses.xml

    r119 r120  
    22  <chapter id="otherclasses">
    33  <title>
    4   Selecting a Node in the Search Tree
     4  Selecting the Next Node in the Search Tree
    55  </title>
    66  <section id="comparison">
    77  <title>CbcCompare - Comparison Methods</title>
    88  <para>
    9   The order in which the nodes of the tree are explored is not predetermined and can be influenced by the user.
    10   CBC provides a abstract base class <classname>CbcCompareBase</classname>
    11   and several instances which are described in <xref linkend="compareTable"/>.
     9  The order in which the nodes of the search tree are explored can strongly influence the performance of branch-and-cut algorithms. CBC give users complete control over the search order. The search order is controlled via the <classname>CbcCompare...</classname> class. CBC provides an abstract base class, <classname>CbcCompareBase</classname>,  and several commonly used instances which are described in <xref linkend="compareTable"/>.
    1210  </para>
    1311    <table frame="none" id="compareTable">
     
    3129      <entry align="left" valign="top">
    3230      This will always choose the node deepest in tree.  It gives minimum
    33       tree size but may take a long time to find best solution.
     31      tree size but may take a long time to find the best solution.
    3432      </entry>
    3533    </row>
     
    5048      </entry>
    5149      <entry align="left" valign="top">
    52       This is designed to do a mostly depth first search until a solution has
    53       been found and then use estimates designed to give a slightly better solution.
    54       If a reasonable number of nodes have been done or a reasonable number of
    55       solutions found then it will go breadth first (i.e. on objective) unless
    56       the tree is very large when it will revert to depth first.  Probably
    57       <classname>CbcCompareUser</classname> described below is better.
     50      This is designed to do a mostly depth-first search until a solution has
     51      been found. It then use estimates that are designed to give a slightly better solution.
     52      If a reasonable number of nodes have been explored (or a reasonable number of
     53      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 <classname>CbcCompareUser</classname> is given below.
    5854      </entry>
    5955    </row>
     
    6359      </entry>
    6460      <entry align="left" valign="top">
    65       If pseudocosts are being used then they can be used to guess a solution.
    66       This just uses guessed solution.
     61      When pseudo costs are invoked, they can be used to guess a solution.  This class uses the guessed solution.
    6762      </entry>
    6863    </row>
     
    7166  </table>
    7267  <para>
    73   It is relatively simple for an advanced user to create new compare class instances.  This describes how to build a new comparison class and the reasoning behind it. This is <filename>CbcCompareUser.hpp</filename> and <filename>CbcCompareUser.cpp</filename> (this code can be found in the CBC Samples directory, see
    74   <xref linkend="moreexamples"/>).  The key <classname>CbcCompare</classname> method is <function>bool test(CbcNode* x, CbcNode* y))</function> which returns true if node <parameter>y</parameter> is better than node <parameter>x</parameter>. In this method the user can easily use the following information available from <classname>CbcModel</classname>.
    75   <table frame="none">
     68  It is relatively simple for an experienced user to create new compare class instances. The code in <xref linkend="test"/> describes how to build a new comparison class and the reasoning behind it. The complete source can be found in <filename>CbcCompareUser.hpp</filename> and <filename>CbcCompareUser.cpp</filename>, located in the CBC Samples directory. See <xref linkend="moreexamples"/>. The key method in <classname>CbcCompare</classname> is <function>bool test(CbcNode* x, CbcNode* y))</function> which returns <parameter>true</parameter> if node <parameter>y</parameter> is preferred over node <parameter>x</parameter>. In the <function>test()</function> method, information from <classname>CbcNode</classname> can easily be used. <xref linkend="nodeTable"/> list some commonly used methods to access information at a node.
     69  <table frame="none" id="nodeTable">
    7670  <title>Information Available from <classname>CbcNode</classname></title>
    7771    <tgroup cols="2">
     
    8276      </entry>
    8377      <entry align="left" valign="top">
    84       Value of objective at that node.
     78      Value of objective at the node.
    8579      </entry>
    8680    </row>
     
    9185      <entry align="left" valign="top">
    9286      Number of unsatisfied integers (assuming branching
    93       object is an integer - otherwise might be number of unsatsified sets).
     87      object is an integer - otherwise it might be number of unsatisfied sets).
    9488      </entry>
    9589    </row>
     
    133127
    134128<para>
    135   There is no information on the state of the tree. If you wanted you could
    136   keep a pointer to the <classname>CbcModel</classname> but the way it is meant to work is that
    137   <function>newSolution()</function> is called whenever a solution is found and <function>every1000Nodes()</function> is called every 1000 nodes.  When these are called the user can modify the
    138   behavior of <function>test()</function>.  Because <classname>CbcNode</classname> has a pointer to the model, the user can also do other things such as changing the maximum time of CBC once a solution has been found (e.g., <function>CbcModel::setMaximumSeconds(double value)</function>). In <filename>CbcCompareUser.cpp</filename> in <filename>COIN/Cbc/Samples</filename> four items of data are used.
     129The 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
     130  <function>newSolution()</function> is called whenever a solution is found and the method <function>every1000Nodes()</function> is called every 1000 nodes.  When these methods are called, the user has the opportunity to modify the
     131  behavior of <function>test()</function> by adjusting their common variables (e.g., <varname>weight_</varname>). Because <classname>CbcNode</classname> 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., <function>CbcModel::setMaximumSeconds(double value)</function>). In <filename>CbcCompareUser.cpp</filename> of the <filename>COIN/Cbc/Samples</filename> directory,  four items of data are used.
    139132</para>
    140133<itemizedlist>
     
    151144  <listitem>
    152145  <para>
    153 3) A weight which is initialized to -1.0
     1463) A weight, <varname>weight_</varname>, which is initialized to -1.0
    154147  </para>
    155148  </listitem>
    156149  <listitem>
    157150  <para>
    158 4) A saved value of weight (for when we set weight back to -1.0 for special reason)
     1514) A saved value of weight, <varname>saveWeight_</varname> (for when weight is set back to -1.0 for special reason)
    159152  </para>
    160153  </listitem>
    161154</itemizedlist>
    162155<para>
    163 The full code for <function>CbcCompareUser::test()</function> is given below.
    164 </para>
    165   <example>
    166   <title>test</title>
     156The full code for the <function>CbcCompareUser::test()</function> method is given in <xref linkend="test"/>.
     157</para>
     158  <example id="test">
     159  <title><function>CbcCompareUser::test()</function></title>
    167160  <programlisting>
    168161  <![CDATA[ 
     
    180173      return x->depth() < y->depth();
    181174  } else {
    182     // after solution
     175    // after solution.
     176    // note: if weight_=0, comparison is based
     177    //       solely on objective value
    183178    double weight = CoinMax(weight_,0.0);
    184179    return x->objectiveValue()+ weight*x->numberUnsatisfied() >
     
    190185  </example>
    191186<para>
    192 Initially, <varname>weight</varname>_ is &lt; 0.0 and we are biased towards depth first.  In
    193 fact, the method prefers <parameter>y</parameter> if <parameter>y</parameter> has fewer unsatisfied variables. In the case of a tie, the method prefers the node with the greater depth in tree.
    194 
    195 Once we get a solution <function>newSolution()</function> is called.  If it was a solution
    196 achieved by branching, <!-- how do can you determine that? --> we work out how much it cost per unsatisfied integer
    197 variable to go from continuous solution to integer solution.  We then set the weight to aim at a slightly better solution.  From then on the method <function>test()</function> returns true if it looks as if <parameter>y</parameter> will lead to a better solution than <parameter>x</parameter>. This is done by <function>newSolution()</function>.
    198 </para>
    199   <example>
    200   <title>newSolution</title>
    201   <programlisting>
    202   <![CDATA[ 
    203 // This allows method to change behavior as it is called
    204 // after each solution
     187Initially, <varname>weight</varname>_ is -1.0 and the search is biased towards depth first.  In
     188fact, <function>test()</function> prefers <parameter>y</parameter> if <parameter>y</parameter> has fewer unsatisfied variables. In the case of a tie, <function>test()</function> prefers the node with the greater depth in tree. Once a solution is found, <function>newSolution()</function> is called. The method <function>newSolution()</function> interacts with <function>test()</function> by means of the variable <varname>weight_</varname>. If the solution was achieved by branching, <!-- how do can you determine that? --> a calculation is made to determine the cost per unsatisfied integer variable to go from the continuous solution to an integer solution.  The variable <varname>weight_</varname> is then set to aim at a slightly better solution.  From then on, <function>test()</function> returns <parameter>true</parameter> if it seems that <parameter>y</parameter> will lead to a better solution than <parameter>x</parameter>. This source for <function>newSolution()</function> in given in <xref linkend="newSolution"/>.
     189</para>
     190  <example id="newSolution">
     191  <title><function>CbcCompareUser::newSolution()</function></title>
     192  <programlisting>
     193  <![CDATA[ 
     194// This allows the test() method to change behavior by resetting weight_.
     195// It is called after each new solution is found.
    205196void
    206197CbcCompareUser::newSolution(CbcModel * model,
     
    209200{
    210201  if (model->getSolutionCount()==model->getNumberHeuristicSolutions())
    211     return; // solution was got by rounding so we ignore
    212   // set to get close to this solution
     202    return; // solution was found by rounding so ignore it.
     203
     204  // set weight_ to get close to this solution
    213205  double costPerInteger =
    214206    (model->getObjValue()-objectiveAtContinuous)/
     
    218210  numberSolutions_++;
    219211  if (numberSolutions_>5)
    220     weight_ =0.0; // this searches on objective
     212    weight_ =0.0; // comparison in test() will be
     213                  // based strictly on objective value.
    221214}
    222215  ]]>   
     
    225218<para>
    226219
    227 But as the search goes on this <!-- what? is "this"? --> may be modified. If a lot of nodes or got a lot of solutions have been genereated, then <varname>weight_</varname> is set to 0.0 so we are doing breadth-first search.  Breadth-first search can lead to an enormous tree. If the tree size is exceeds 10000, then we may desire to go back to a search biased towards depth first. Changing the behaviour done by the method <function>every1000Nodes</function>.
    228   </para>
    229   <example>
    230   <title>newSolution</title>
    231   <programlisting>
    232   <![CDATA[ 
    233 // This allows method to change behavior
     220As the search progresses, the comparison can be <!-- what? is "this"? -->modified. If many nodes (or many solutions) have been genereated, then <varname>weight_</varname> 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 <function>every1000Nodes</function> shown in <xref linkend="everyK"/>.
     221  </para>
     222  <example id="everyK">
     223  <title><function>CbcCompareUser::every1000Nodes()</function></title>
     224  <programlisting>
     225  <![CDATA[ 
     226// This allows the test() method to change behavior every so often
    234227bool
    235228CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
    236229{
    237230  if (numberNodes>10000)
    238     weight_ =0.0; // this searches on objective
     231    weight_ =0.0; // compare nodes based on objective value
    239232  else if (numberNodes==1000&&weight_==-2.0)
    240233    weight_=-1.0; // Go to depth first
     
    259252<chapter id="hueristicChap">
    260253  <title>
    261   Using Hueristics in CBC
     254  Getting Good Bounds in CBC
    262255  </title>
    263256  <section id="heuristics">
    264257  <title>CbcHeuristic - Heuristic Methods</title>
    265258  <para>
    266   In practice, it is very useful to get a good solution reasonably fast.
    267   A good bound will greatly reduce the run time and good solutions can satisfy the user
     259  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
    268260  on very large problems where a complete search is impossible.  Obviously, heuristics are
    269   problem dependent although some have more general use.
    270   At present there is only one in CBC itself. Hopefully, the number of heuristics will grow.
    271   Other hueristics are in the <filename>COIN/Cbc/Samples</filename>
     261  problem dependent, although some do have more general use.
     262  At present there is only one heuristic in CBC itself, <classname>CbcRounding</classname>. Hopefully, the number will grow. Other heuristics are in the <filename>COIN/Cbc/Samples</filename>
    272263  directory.  A heuristic tries to obtain a solution to the original
    273264  problem so it only needs to consider the original rows and does not have to use the
    274   current bounds.
    275   One to use a greedy heuristic designed for use in the miplib problem
    276   fast0507 will be developed later in this section. <!-- huh? -->
    277   CBC provides an abstract base class <classname>CbcHeuristic</classname> and a rounding heuristic in CBC.
    278   </para>
    279   <para>
    280   This describes how to build a greedy heuristic for a set covering problem.
    281    A more general version is in <filename>CbcHeuristicGreedy.hpp</filename> and
    282    <filename>CbcHeuristicGreedy.cpp</filename> which can be found in the <filename>COIN/Cbc/Samples</filename> directory, see <xref linkend="moreexamples"/>.
    283 
    284   The heuristic we will code will leave all variables which are at one at this node of the
    285   tree to that value and will
    286   initially set all others to zero.  We then sort all variables in order of their cost
    287   divided by the number of entries in rows which are not yet covered.  We may randomize that
    288   value a bit so that ties will be broken in different ways on different runs of the heuristic.
    289   We then choose the best one and set it to one and repeat the exercise. Because this is
    290   a set covering problem &ge; we are guaranteed to find a solution (not necessarily a
    291   better one though).  We could
    292   improve the speed by just redoing those affected but in this text we will keep it simple.
    293   Also if all elements are 1.0 then we could do faster.
    294   The key CbcHeuristic method is <function>int&nbsp;solution(double &amp; solutionValue,
    295                                               double&nbsp;*&nbsp;betterSolution)</function>
    296   which returns 0 if no solution found and 1 if found when it fills in the objective value
    297   and primal solution.  The actual code in <filename>CbcHeuristicGreedy.cpp</filename> is
    298   a little more complicated but this will work and gives the basic idea.  For instance
    299   the code here assumes all variables are integer.
    300   The important bit of data is a copy of the matrix (stored by column)
    301   before any cuts have been made.  The data used are bounds, objective and the matrix
    302   plus two work arrays.
     265  current bounds. CBC provides an abstract base class <classname>CbcHeuristic</classname> and a rounding heuristic in CBC. <!-- rlh: we need an example of using an existing heuristic -->
     266  </para>
     267  <para>
     268  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 <filename>CbcHeuristicGreedy.hpp</filename> and <filename>CbcHeuristicGreedy.cpp</filename> located in the <filename>COIN/Cbc/Samples</filename> directory, see <xref linkend="moreexamples"/>.
     269</para>
     270<para>
     271  The greedy heuristic will leave all variables taking value one at this node of the
     272  tree at value one, and will initially set all other variable to value zero. 
     273  All variables are then sorted in order of their cost
     274  divided by the number of entries in rows which are not yet covered. (We may randomize that
     275  value a bit so that ties will be broken in different ways on different runs of the heuristic.)
     276  The best one is choosen, and set to one. The process is repeated. Because this is
     277  a set covering problem (i.e., all constraints are &ge;), 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).
     278</para>
     279<para>
     280  The key <classname>CbcHeuristic</classname> method is <function>int&nbsp;solution(double &amp; solutionValue,
     281                                              double&nbsp;*&nbsp;betterSolution)</function>.
     282  The <function>solution()</function> 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 <filename>CbcHeuristicGreedy.cpp</filename> 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.
    303283  </para>
    304284  <example>
     
    331311  </example>
    332312<para>
    333 Then we initialize newSolution as rounded down solution.
     313The <varname>newSolution</varname> is then initialized to the rounded down solution.
    334314</para>
    335315  <example>
    336   <title>initialize newSolution</title>
     316  <title>Initialize <varname>newSolution</varname></title>
    337317  <programlisting>
    338318  <![CDATA[ 
     
    361341  </example>
    362342<para>
    363 Now some row activities will be below their lower bound so
    364 we then find the variable which is cheapest in reducing the sum of
    365 infeasibilities.  We then repeat.  This is a finite process and could be coded
    366 to be faster but this is simplest.
     343<!-- rlh: where is "direction" from? -->
     344
     345At 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.)
    367346  </para>
    368347  <example>
    369   <title>Create feasible new solution</title>
     348  <title>Create Feasible <varname>newSolution</varname> from Initial <varname>newSolution</varname></title>
    370349  <programlisting>
    371350  <![CDATA[ 
     
    416395  </example>
    417396<para>
    418 We have finished so now we need to see if solution is better and doublecheck
    419 we are feasible.
     397A solution value of <varname>newSolution</varname> is compared to the best solution value. If <varname>newSolution</varname> is an improvement, its feasibility is validated.
    420398  </para>
    421399  <example>
    422   <title>Check good solution</title>
     400  <title>Check Solution Quality of <varname>newSolution</varname></title>
    423401  <programlisting>
    424402  <![CDATA[ 
    425403  returnCode=0; // 0 means no good solution
    426   if (newSolutionValue<solutionValue) {
     404  if (newSolutionValue<solutionValue) { // minimization
    427405    // check feasible
    428406    memset(rowActivity,0,numberRows*sizeof(double));
     
    465443 </title>
    466444  <section id="branching">
    467   <title>Branching</title>
    468   <para>
    469 If the user declares variables as integer but does no more, then Cbc will treat them
    470 as simple integer variables.  In many cases the user would like to do some more fine tuning.  This shows how to create integer variables with pseudo costs.  When pseudo costs are given then
    471 it 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.  This can be used both for branching and for choosing a node.
    472    The full code is in <filename>longthin.cpp</filename>
    473   (this code can be found in the CBC Samples directory, see
    474   <xref linkend="moreexamples"/>). 
     445  <title>Pseudo Cost Branching</title>
     446  <para>
     447<!-- rlh: need a description of "objects" -->
     448If the user declares variables as integer but does no more, then CBC will treat them
     449as 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
     450it 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.
     451   The full code is in <filename>longthin.cpp</filename> located in the CBC Samples directory, see
     452  <xref linkend="moreexamples"/>.
     453</para>
     454<para> 
    475455  The idea is simple for set covering problems.
    476   Branching up gets us much closer to an integer solution so we want
    477   to encourage up - so we will branch up if variable value > 0.333333.
     456  Branching up gets us much closer to an integer solution so we will encourage that direction by branch up if variable value > 0.333333.
    478457  The expected cost of going up obviously depends on the cost of the
    479   variable so we just choose pseudo costs to reflect that.
    480   </para>
    481   <example>
    482   <title>Pseudo costs</title>
     458  variable. The pseudo costs are choosen to reflect that fact.
     459<!-- rlh: what's the difference between simple var objects and pseudo cost objects? explain. -->
     460  </para>
     461  <example id="pseudo">
     462  <title><classname>CbcSimpleIntegerPseudoCosts</classname></title>
    483463  <programlisting>
    484464  <![CDATA[ 
     
    509489  </example>
    510490<para>
    511 The actual coding in the example also tries to give more importance to variables with more
     491The code in <xref linkend="pseudo"/> also tries to give more importance to variables with more
    512492coefficients.  Whether this sort of thing is worthwhile should be the subject of experimentation.
    513 Here is another example which is for crew scheduling problems.  In this case the problem has
    514 few rows but many thousands of variables.  Branching a variable to 1 is very powerful as it
    515 fixes many other variables to zero, but branching to zero is very weak as thousands of variables
    516 can increase from zero.  But in crew scheduling each constraint is a flight leg e.g. JFK to DFW.
    517 From DFW (Dallas) there may be several flights the crew could take next - suppose one flight is
    518 the 9:30 flight from DFW to LAX (Los Angeles).  Then a binary branch is that the crew arriving
    519 at DFW either take the 9:30 flight to LAX or they don't.  This follow-on branching does not
    520 fix individual variables but instead divides all the variables with entries in the JFK-DFW
     493<!-- needs more explaination, e.g., why do you have to delete objects? -->
     494<!-- what does a pseudo cost object do for you? and how does it do it? -->
     495</para>
     496</section>
     497  <section id="followOn">
     498  <title>Follow-On Branching</title>
     499  <para>
     500In 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.
     501From DFW there may be several flights the crew could take next - suppose one flight is
     502the 9:30 flight from DFW to LAX airport.  A binary branch is that the crew arriving
     503at DFW either take the 9:30 flight to LAX or they don't.  This "follow-on" branching does not
     504fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW
    521505constraint into two groups - those with entries in the DFW-LAX constraint and those without
    522506entries.
    523    The full code is in <filename>crew.cpp</filename>
    524   (this code can be found in the CBC Samples directory, see
    525   <xref linkend="moreexamples"/>).  In this case we may as well leave the simple integer
    526 variables and we may have to if there are other sorts of constraints.  But we want to
    527 branch on the follow-on rules first so we use priorities to say that those are the
    528 important ones.
     507</para>
     508<para>
     509   The full sample code for follow-on brancing is in <filename>crew.cpp</filename>
     510  located in the CBC Samples directory, see
     511  <xref linkend="moreexamples"/>).  In this case, the simple integer
     512variables 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.
     513<!-- rlh:need to explain how *priorities* work, and where they are used -->
    529514</para>
    530515  <example>
    531   <title>Follow-on branching</title>
     516  <title><classname>CbcFollowOn</classname></title>
    532517  <programlisting>
    533518  <![CDATA[ 
    534519  int iColumn;
    535520  int numberColumns = solver3->getNumCols();
    536   /* We are going to add a single follow on object but we
     521  /* We are going to add a single follow-on object but we
    537522     want to give low priority to existing integers
    538523     As the default priority is 1000 we don't actually need to give
     
    547532    }
    548533  }
    549   /* Second parameter is true if we are adding objects,
    550      false if integers.  So this does integers */
     534  /* Second parameter is set to true for objects,
     535     and false for integers. This indicates integers */
    551536  model.passInPriorities(priority,false);
    552537  delete [] priority;
    553   /* Add in objects before we can give priority.
    554      In this case just one - but this shows general method
     538  /* Add in objects before we can give them a priority.
     539     In this case just one object
     540     - but it shows the general method
    555541  */
    556542  CbcObject ** objects = new CbcObject * [1];
     
    565551  </programlisting>
    566552  </example>
     553<!-- rlh: need to explain the CbcFollowOn object -->
    567554  </section>
    568555</chapter>
    569556<chapter id="SolverChap">
    570557<title>
    571 Advance Use of Solver
     558  Advance Solver Uses
    572559</title>
    573560  <section id="solver">
    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.
    577   This does not give much flexibility so advanced users can inherit from the interface
    578   of choice.  This describes such a solver for a long thin problem e.g. fast0507 again.
    579   As with all these examples it is not guaranteed that this is the fastest way to solve
    580   any of these problems - they are to illustrate techniques.
    581    The full code is in <filename>CbcSolver2.hpp</filename> and
    582    <filename>CbcSolver2.cpp</filename>
    583   (this code can be found in the CBC Samples directory, see
    584   <xref linkend="moreexamples"/>).
    585   <function>initialSolve</function> is called a few times so although we will not gain much
    586   this is a simpler place to start.  The example derives from <classname>OsiClpSolverInterface</classname> and the code
    587   is:
    588   </para>
    589   <example>
    590   <title>initialSolve</title>
     561  <title>Creating a Solver via Inheritance</title>
     562  <para>
     563  CBC uses a generic <classname>OsiSolverInterface</classname> and its <function>resolve</function> capability.
     564  This does not give much flexibility so advanced users can inherit from their interface
     565  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 <filename>CbcSolver2.hpp</filename> and <filename>CbcSolver2.cpp</filename> located in the CBC Samples directory, see
     566  <xref linkend="moreexamples"/>.
     567</para>
     568<para>
     569The method <function>initialSolve</function> is called a few times in CBC, and provides a convenient starting point. The <varname>modelPtr_</varname> derives from <classname>OsiClpSolverInterface</classname>.
     570  </para>
     571  <example id="initialSolve">
     572  <title><function>initialSolve()</function></title>
    591573  <programlisting>
    592574  <![CDATA[ 
     
    606588  </programlisting>
    607589  </example>
    608 <para>
    609 The <function>resolve</function> method is more complicated.  The main pieces of data are
    610 a counter <varname>count_</varname>which is incremented each solve and an int array <varname>node_</varname> which stores the last time
    611 a variable was active in a solution.  For the first few times normal dual is called and
     590<!-- rlh: need a verbal description to go with the intialSolve() code -->
     591<para>
     592The <function>resolve()</function> method is more complicated than <function>initialSolve()</function>.  The main pieces of data are a counter <varname>count_</varname> which is incremented each solve and an integer array <varname>node_</varname> which stores the last time
     593a variable was active in a solution.  For the first few times, the normal Dual Simplex is called and
    612594<varname>node_</varname> array is updated.
    613595</para>
    614596  <example>
    615   <title>First few solves</title>
     597  <title>First Few Solves</title>
    616598  <programlisting>
    617599  <![CDATA[ 
     
    634616  </programlisting>
    635617  </example>
    636 <para>
    637 After the first few solves we only use those which took part in a solution in the last so many
    638 solves.  As fast0507 is a set covering problem we can also take out any rows which are
    639 already covered.
     618<!-- rlh: need more explanation of what's being illustrated in the code -->
     619<para>
     620After the first few solves, only those variables which took part in a solution in the last so many
     621solves are used.  As fast0507 is a set covering problem, any rows which are already covered can be taken out.
    640622  </para>
    641623  <example>
    642   <title>Create small problem</title>
     624  <title>Create Small Problem</title>
    643625  <programlisting>
    644626  <![CDATA[ 
     
    737719  </example>
    738720<para>
    739 If the variables cover the rows then we know that the problem is feasible (we are not using
    740 cuts).  If the rows
    741 were E rows then this might not be the case and we would have to do more work.  When we have solved
    742 then we see if there are any negative reduced costs and if there are then we have to go to the
    743 full problem and use primal to clean up.
     721If the variables cover the rows, then the problem is feasible (no cuts are being used). If the rows
     722were 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.
    744723  </para>
    745724  <example>
    746   <title>Check optimal solution</title>
     725  <title>Check Optimal Solution</title>
    747726  <programlisting>
    748727  <![CDATA[ 
     
    783762        nBad++;
    784763    }
    785     // If necessary claen up with primal (and save some statistics)
     764    // If necessary clean up with primal (and save some statistics)
    786765    if (nBad) {
    787766      timesBad_++;
     
    793772  </example>
    794773<para>
    795 We then update <varname>node_</varname> array as for the first few solves.  To give some idea of the effect of this
    796 tactic fast0507 has 63,009 variables and the small problem never has more than 4,000 variables.
    797 In just over ten percent of solves did we have to resolve and then the average number of iterations
     774The array <varname>node_</varname> 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
    798775on full problem was less than 20.
    799 To give another example - again only for illustrative purposes it is possible to do quadratic
    800 mip.  In this case we make <function>resolve</function> the same as
     776</para>
     777</section>
     778 <section id="quadratic">
     779  <title>Quadratic MIP</title>
     780<para>
     781To give another example - again only for illustrative purposes -- it is possible to do quadratic
     782MIP with CBC.  In this case, we make <function>resolve</function> the same as
    801783<function>initialSolve</function>.
    802784   The full code is in <filename>ClpQuadInterface.hpp</filename> and
    803    <filename>ClpQuadInterface.cpp</filename>
    804   (this code can be found in the CBC Samples directory, see
     785   <filename>ClpQuadInterface.cpp</filename> located in the CBC Samples directory, see
    805786  <xref linkend="moreexamples"/>).
    806787  </para>
    807788  <example>
    808   <title>Solve a quadratic mip</title>
     789  <title>Solving a Quadratic MIP</title>
    809790  <programlisting>
    810791  <![CDATA[ 
Note: See TracChangeset for help on using the changeset viewer.