Ignore:
Timestamp:
May 10, 2005 11:40:19 AM (14 years ago)
Author:
rlh
Message:

updated the user guide

File:
1 edited

Legend:

Unmodified
Added
Removed
  • html/trunk/Cbc/ch03s02.html

    r554 r557  
    1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>CbcHeuristic - heuristic methods</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2"><link rel="home" href="index.html" title="CBC User Guide"><link rel="up" href="ch03.html" title="Chapter 3. 
    2   Other Classes and examples
    3   "><link rel="previous" href="ch03.html" title="Chapter 3. 
    4   Other Classes and examples
    5   "><link rel="next" href="ch03s03.html" title="Branching"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">CbcHeuristic - heuristic methods</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><th width="60%" align="center">Chapter 3. 
    6   Other Classes and examples
    7   </th><td width="20%" align="right"> <a accesskey="n" href="ch03s03.html">Next</a></td></tr></table><hr></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="heuristics"></a>CbcHeuristic - heuristic methods</h2></div></div><div></div></div><p>
    8   For practical use it is very useful to be able to get a good solution reasonably fast.
     1<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?>
     2<html xmlns="http://www.w3.org/1999/xhtml"><head><title>CbcHeuristic - Heuristic Methods</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2"/><link rel="home" href="index.html" title="CBC User Guide"/><link rel="up" href="ch03.html" title="Chapter 3. &#10;  Selecting a Node in the Search Tree&#10;  "/><link rel="previous" href="ch03.html" title="Chapter 3. &#10;  Selecting a Node in the Search Tree&#10;  "/><link rel="next" href="ch04.html" title="Chapter 4. &#10;  Branching&#10; "/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">CbcHeuristic - Heuristic Methods</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><th width="60%" align="center">Chapter 3. 
     3  Selecting a Node in the Search Tree
     4  </th><td width="20%" align="right"> <a accesskey="n" href="ch04.html">Next</a></td></tr></table><hr/></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="heuristics"/>CbcHeuristic - Heuristic Methods</h2></div></div><div/></div><p>
     5  In practice, it is very useful to get a good solution reasonably fast.
    96  A good bound will greatly reduce the run time and good solutions can satisfy the user
    10   on very large problems where a complete search is impossible.  Heuristics are obviously
    11   problem dependant although some have more general use.  I hope to increase the number.
    12   At present there is only one in Cbc itself although there are others in the Samples
    13   directory.  The heuristic is trying to obtain a solution to the original
    14   problem so it need only consider original rows and does not have to use the
     7  on very large problems where a complete search is impossible.  Obviously, heuristics are
     8  problem dependent although some have more general use.
     9  At present there is only one in CBC itself. Hopefully, the number of heuristics will grow.
     10  Other hueristics are in the <tt class="filename">COIN/Cbc/Samples</tt>
     11  directory.  A heuristic tries to obtain a solution to the original
     12  problem so it only needs to consider the original rows and does not have to use the
    1513  current bounds.
    1614  One to use a greedy heuristic designed for use in the miplib problem
    17   fast0507 will be developed later in this section.
    18   Cbc provides a abstract base class CbcHeuristic and a rounding heuristic in Cbc.
     15  fast0507 will be developed later in this section. 
     16  CBC provides an abstract base class <tt class="classname">CbcHeuristic</tt> and a rounding heuristic in CBC.
    1917  </p><p>
    2018  This describes how to build a greedy heuristic for a set covering problem.
    2119   A more general version is in <tt class="filename">CbcHeuristicGreedy.hpp</tt> and
    22    <tt class="filename">CbcHeuristicGreedy.cpp</tt>
    23   (this code can be found in the CBC Samples directory, see
    24   <a href="ch05.html" title="Chapter 5. 
     20   <tt class="filename">CbcHeuristicGreedy.cpp</tt> which can be found in the <tt class="filename">COIN/Cbc/Samples</tt> directory, see <a href="ch06.html" title="Chapter 6. &#10;More Samples&#10;">Chapter 6, <i>
    2521More Samples
    26 ">Chapter 5, <i>
    27 More Samples
    28 </i></a>).
     22</i></a>.
    2923
    3024  The heuristic we will code will leave all variables which are at one at this node of the
     
    4741  before any cuts have been made.  The data used are bounds, objective and the matrix
    4842  plus two work arrays.
    49   </p><div class="example"><a name="id2903012"></a><p class="title"><b>Example 3.4. Data</b></p><pre class="programlisting">
     43  </p><div class="example"><a id="id2984921"/><p class="title"><b>Example 3.4. Data</b></p><pre class="programlisting">
    5044   
    5145  OsiSolverInterface * solver = model_-&gt;solver(); // Get solver from CbcModel
     
    7367  </pre></div><p>
    7468Then we initialize newSolution as rounded down solution.
    75 </p><div class="example"><a name="id2903038"></a><p class="title"><b>Example 3.5. initialize newSolution</b></p><pre class="programlisting">
     69</p><div class="example"><a id="id2984946"/><p class="title"><b>Example 3.5. initialize newSolution</b></p><pre class="programlisting">
    7670   
    7771  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
     
    10195infeasibilities.  We then repeat.  This is a finite process and could be coded
    10296to be faster but this is simplest.
    103   </p><div class="example"><a name="id2903094"></a><p class="title"><b>Example 3.6. Create feasible new solution</b></p><pre class="programlisting">
     97  </p><div class="example"><a id="id2984998"/><p class="title"><b>Example 3.6. Create feasible new solution</b></p><pre class="programlisting">
    10498   
    10599  while (true) {
     
    149143We have finished so now we need to see if solution is better and doublecheck
    150144we are feasible.
    151   </p><div class="example"><a name="id2903189"></a><p class="title"><b>Example 3.7. Check good solution</b></p><pre class="programlisting">
     145  </p><div class="example"><a id="id2985096"/><p class="title"><b>Example 3.7. Check good solution</b></p><pre class="programlisting">
    152146   
    153147  returnCode=0; // 0 means no good solution
     
    183177  }
    184178     
    185   </pre></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch03.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch03s03.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 3. 
    186   Other Classes and examples
    187    </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Branching</td></tr></table></div></body></html>
     179  </pre></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch03.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch04.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 3. 
     180  Selecting a Node in the Search Tree
     181   </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 4. 
     182  Branching
     183 </td></tr></table></div></body></html>
Note: See TracChangeset for help on using the changeset viewer.