source: html/trunk/Cbc/ch01.html @ 554

Last change on this file since 554 was 554, checked in by rlh, 16 years ago

initial import of Cbc documentation

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.9 KB
Line 
1<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Chapter 1. 
2    Introduction
3  </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="index.html" title="CBC User Guide"><link rel="previous" href="index.html" title="CBC User Guide"><link rel="next" href="ch01s02.html" title="
4  Prerequisites
5  "></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">Chapter 1. 
6    Introduction
7  </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="index.html">Prev</a> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="ch01s02.html">Next</a></td></tr></table><hr></div><div class="chapter" lang="en"><div class="titlepage"><div><div><h2 class="title"><a name="intro"></a>Chapter 1. 
8    Introduction
9  </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="ch01.html#id2826645">
10  Welcome to CBC
11  </a></dt><dt><a href="ch01s02.html">
12  Prerequisites
13  </a></dt></dl></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="id2826645"></a>
14  Welcome to CBC
15  </h2></div></div><div></div></div><p>
16  COIN Branch and Cut or CBC is an open-source mixed integer solver written
17  in C++.  It is primarily meant to be used as a callable library, but a
18  basic, stand-alone do link **** link linkend="cbcexe"executable version is also
19  available.  This Branch and Cut solver relies on many other parts of the COIN
20  repository.  So it relies on Cgl for cut generators and any cut generator written to
21  CGL standards may be used in CBC.  Again some of these cut generators e.g. Gomory cuts
22  rely on the factorization functionality of CoinFactorization.  CBC needs a linear solver
23  and uses the Osi (Open Solver Interface) interface to access the linaer solver so
24  many solvers may be used.  However the most common use is expected to be when
25  using COIN's native linear Solver - CLP.
26  </p><p>
27  Before examining CBC in more detail it may be helpful to give a very brief description
28  of Branch and Cut (which should really be called Branch and Cut and Bound).  If some
29  variables in the model must take on integer values e.g. 0,1 or 2 then the integrality
30  requirement is relaxed and a lower bound of 0.0 and an upper bound of 2.0 put on the
31  variable(s). This linear model can be solved using a solver.  If all "integer"
32  variables take integer values then we are finished;  if not we choose one non-integral
33  variable e.g. with value 1.3 (A) (B) and create two linear models - one with the variable
34  having an upper bound of 1.0 and the other with a lower bound of 2.0.  We then put
35  these two models on our tree of models and solve one of them.  We repeat the process
36  taking one model off our tree (C) (D) and repeating the process.  As every time we
37  branch we tighten the problem so the objective value can not improve.  So if we
38  obtain a valid solution we can use that as a bound to prune the tree.  If we
39  try and make the linear models more integral by using Cuts then it is termed
40  Branch and Cut (E) (F).
41  </p><div class="table"><a name="id2826677"></a><p class="title"><b>Table 1.1. Associated classes</b></p><table summary="Associated classes" border="0"><colgroup><col><col><col></colgroup><thead><tr><th>
42    Note
43    </th><th>
44    Class name
45    </th><th>
46    Description
47    </th></tr></thead><tbody><tr><td align="left" valign="top">
48      (A)
49      </td><td align="left" valign="top">
50      CbcBranch...
51      </td><td align="left" valign="top">
52      These classes define what is the nature of discontinuity.  The simplest
53      are variables which must take an integral value but there others
54      which will be described later e.g. lotsizing variables. 
55      </td></tr><tr><td align="left" valign="top">
56      (B)
57      </td><td align="left" valign="top">
58      CbcNode
59      </td><td align="left" valign="top">
60      This is the class that decides which variable/entity  to branch on next.
61      Even advanced users will probably only interact with this by setting
62      CbcModel parameters e.g. priorities.
63      </td></tr><tr><td align="left" valign="top">
64      (C)
65      </td><td align="left" valign="top">
66      CbcTree
67      </td><td align="left" valign="top">
68      All unsolved models can be thought of as being on a tree where each
69      model can branch two or more times.  The user should not need to be
70      concerned with this class.
71      </td></tr><tr><td align="left" valign="top">
72      (D)
73      </td><td align="left" valign="top">
74      CbcCompare...
75      </td><td align="left" valign="top">
76      All unsolved models are in a tree but which leaf do we choose.  These
77      classes are very small simple ones which can be tailored to suit the problem.
78      </td></tr><tr><td align="left" valign="top">
79      (E)
80      </td><td align="left" valign="top">
81      CglCutGenerators
82      </td><td align="left" valign="top">
83      Any cut generator from Cgl can be given to the model to be used with parameters
84      which modify when each generator will be tried.  Few people will write their
85      own cut generators but all should see which are effective.
86      </td></tr><tr><td align="left" valign="top">
87      (F)
88      </td><td align="left" valign="top">
89      CbcHeuristics
90      </td><td align="left" valign="top">
91      Heuristics are very important for obtaining valid solutions quickly.  Some
92      are available but this is an area where it is useful and interesting to
93      write specialized ones.
94      </td></tr></tbody></table></div><p>
95  There are a number of resources available to help new CBC users get started.
96  This document is designed to be used in conjunction with the files in the
97  Samples subdirectory of the main CBC directory (<tt class="filename">COIN/Cbc/Samples</tt>).
98  The Samples illustrate how to use CBC and may also serve as useful starting points
99  for user projects.  In the event that either this document or the available
100  <a href="apb.html" title="Appendix B. Doxygen">Doxygen content</a> conflicts with the observed
101  behavior of the source code, the comments in the header files, found in
102  <tt class="filename">COIN/Cbc/include</tt>, are the ultimate reference.
103  </p></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="index.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="index.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch01s02.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">CBC User Guide </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 
104  Prerequisites
105  </td></tr></table></div></body></html>
Note: See TracBrowser for help on using the repository browser.