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> |
---|