File: intro.xml

package info (click to toggle)
coinor-cbc 2.9.9+repack1-1
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 7,848 kB
  • ctags: 5,787
  • sloc: cpp: 104,337; sh: 8,921; xml: 2,950; makefile: 520; ansic: 491; awk: 197
file content (231 lines) | stat: -rw-r--r-- 10,219 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<?xml version="1.0" encoding="ISO-8859-1"?>
  <chapter id="intro">
  <title>
    Introduction
  </title>
  <section>
  <title>
  Welcome to CBC
  </title>
  <para>
  The COIN 
    <footnote>
        <para>
	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". 
	</para>
      </footnote>
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-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.
 </para>
 </section>

  <section>
  <title>
  Prerequisites
  </title>
  <para>
  The primary users of CBC are expected to be developers implementing customized branch-and-cut algorithms in C++ using CBC as a library. Consequently, this document assumes a working knowledge of 
  <ulink url="http://www.cplusplus.com/doc/tutorial/">C++</ulink>, including basic
  object-oriented programming terminology, and familiarity with the fundamental concepts of
  <ulink url="http://carbon.cudenver.edu/~hgreenbe/courseware/LPshort/intro.html">
  linear programming</ulink> and
  <ulink url="http://carbon.cudenver.edu/~hgreenbe/courseware/MIP/intro.html">
  mixed integer programming</ulink>. <!-- any better mip links? -->
  </para>

  <para>
<!-- dependencies -->
CBC 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.
</para>
<para>
Technically 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.  
 <!-- need a link to OSI and CGL documentation. Shoot, need OSI and CGL documentation! -->
 </para>
<para>
In summary, readers should have the following prerequisites:
   <itemizedlist>
    <listitem>
    <simpara>
    C++ knowledge,
    </simpara>
    </listitem>
    <listitem>
    <simpara>
    LP and MIP fundamentals, and    
    </simpara>
    </listitem>
    <listitem>
    <simpara>
    OSI familiarity. 
    </simpara>
    </listitem>
    </itemizedlist>
</para>
<para>
Unless otherwise stated, we will assume the problem being optimized is a minimization problem. The terms "model" and "problem" are used synonymously.
</para>
 </section>

<section>
<title>
Branch-and-Cut Overview
</title>
  <para>
  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"/>.
 </para>

  <para>
Step 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.   
 </para>
 <para>  
Step 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.
 </para>
 <para>
While (search tree is not empty) { 
</para>
<para> 
   Step 3. (Choose Node) Pick a node off the tree (C)(D)
</para>
<para>
   Step 4. (Re-optimize LP) Create an LP relaxation and solve.
</para>
<para>
   Step 5. (Bound) Interrogate the optimal LP solution, and try to prune the node by one of the following.
   <itemizedlist>
    <listitem>
    <simpara>
    LP is infeasible, prune the node.
    </simpara>
    </listitem>
    <listitem>
    <simpara>
    Else, the optimal LP solution value of the node exceeds the current upper bound, prune the node.  
    </simpara>
    </listitem>
    <listitem>
    <simpara>
    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.          
    </simpara>
    </listitem>
    </itemizedlist>  
</para>
<para>
   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.
}
 </para>
 <para>      
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 only used in Step 1, the method is called a "cut-and-branch" algorithm.)
 
  <!-- rlh: this explaination is for people who already know b&c -->
  </para>
  <table frame="none" id="assClasses">
  <title>Associated Classes</title>
    <tgroup cols="3">
    <thead>
    <row>
    <entry>
    Note
    </entry>
    <entry>
    Class name
    </entry>
    <entry>
    Description
    </entry>
    </row>
    </thead>
    <tbody>
    <row>
      <entry align="left" valign="top">
      (A)
      </entry>
      <entry align="left" valign="top">
      <classname>CbcBranch...</classname>
      </entry>
      <entry align="left" valign="top">
      These classes define the nature of MIP's discontinuity.  The simplest discontinuity
      is a variable which must take an integral value. Other types of discontinuities 
      exist, e.g., lot-sizing variables. 
      <!--rlh: why "...."? Currently 4: CbcBranchActual.cpp, CbcBranchBase.cpp CbcBranchCut.cpp, CbcBranchLotsizes.cpp--> 
      </entry>
    </row>
    <row>
      <entry align="left" valign="top">
      (B)
      </entry>
      <entry align="left" valign="top">
      <classname>CbcNode</classname>
      </entry>
      <entry align="left" valign="top">
      This class decides which variable/entity to branch on next.
      Even advanced users will probably only interact with this class by setting
      <classname>CbcModel</classname> parameters ( e.g., priorities).
      </entry>
    </row>
    <row>
      <entry align="left" valign="top">
      (C)
      </entry>
      <entry align="left" valign="top">
      <classname>CbcTree</classname>
      </entry>
      <entry align="left" valign="top">
      All unsolved models can be thought of as being nodes on a tree where each
      node (model) can branch two or more times.  The user should not need to be
      concerned with this class.
      </entry>
    </row>
    <row>
      <entry align="left" valign="top">
      (D)
      </entry>
      <entry align="left" valign="top">
      <classname>CbcCompare...</classname>
      </entry>
      <entry align="left" valign="top">
      These classes are used in determine which of the unexplored nodes in the tree to consider next. These
      classes are very small simple classes that can be tailored to suit the problem.
      <!--rlh: Classes? Currently only 1: CbcCompateActual.cpp-->
      </entry>
    </row>
    <row>
      <entry align="left" valign="top">
      (E)
      </entry>
      <entry align="left" valign="top">
      <classname>CglCutGenerators</classname>
      </entry>
      <entry align="left" valign="top">
      Any cut generator from CGL can be used in CBC. The cut generators are passed to CBC with parameters
      which modify when each generator will be tried. All cut generators should be tried to 
      determine which are effective. Few users will write their own cut generators.
      </entry>
    </row>
    <row>
      <entry align="left" valign="top">
      (F)
      </entry>
      <entry align="left" valign="top">
      <classname>CbcHeuristics</classname>
      </entry>
      <entry align="left" valign="top">
      Heuristics are very important for obtaining valid solutions quickly.  Some
      heuristics are available, but this is an area where it is useful and interesting to
      write specialized ones.
      </entry>
    </row>
    </tbody>
  </tgroup>
  </table>
<para>
  There are a number of resources available to help new CBC users get started.
  This document is designed to be used in conjunction with the files in the
  Samples subdirectory of the main CBC directory (<filename>COIN/Cbc/Samples</filename>).
  The Samples illustrate how to use CBC and may also serve as useful starting points
  for user projects.  In the event that either this document or the available
  <link linkend="doxygen">Doxygen content</link> conflicts with the observed
  behavior of the source code, the comments in the header files, found in
  <filename>COIN/Cbc/include</filename>, are the ultimate reference.
  </para>
  </section>

  </chapter>