source: branches/gh-pages/intro.md @ 2521

Last change on this file since 2521 was 2521, checked in by stefan, 2 months ago

migrate Cbc documentation to gh-pages

  • converted docbook to markdown
  • source now in gh-pages branch, so remove Cbc/doc
  • some cleanup
  • update link in README.md
  • Property svn:eol-style set to native
File size: 7.5 KB
Line 
1# Introduction
2
3The COIN-OR Branch and Cut solver (CBC) is an open-source
4mixed-integer program (MIP) solver written in C++. CBC is intended to be
5used primarily as a callable library to create customized branch-and-cut
6solvers. A basic, stand-alone executable version is also available. CBC
7is an active open-source project led by John Forrest at www.coin-or.org.
8
9## Prerequisites
10
11The primary users of CBC are expected to be developers implementing
12customized branch-and-cut algorithms in C++ using CBC as a library.
13Consequently, this document assumes a working knowledge of
14[C++](http://www.cplusplus.com/doc/tutorial/), including basic
15object-oriented programming terminology, and familiarity with the
16fundamental concepts of [linear programming](http://carbon.cudenver.edu/~hgreenbe/courseware/LPshort/intro.html)
17and [mixed integer programming](http://carbon.cudenver.edu/~hgreenbe/courseware/MIP/intro.html).
18
19CBC relies other parts of the COIN-OR repository. CBC needs an LP solver
20and relies the COIN-OR Open Solver Inteface (OSI) to communicate with the
21user's choice of solver. Any LP solver with an OSI interface can be used
22with CBC. The LP solver expected to be used most commonly is COIN-OR's
23native linear program solver, CLP. For cut generators, CBC relies on the
24COIN-OR Cut Generation Library (CGL). Any cut generator written to CGL
25standards can be used with CBC. Some of the cut generators in CGL rely
26on other parts of COIN, e.g., CGL's Gomory cut generator rely on the
27factorization functionality of `CoinFactorization`. This document
28assumes basic familiarity with OSI and CGL.
29
30Technically speaking, CBC assesses the solver (and sometime the model
31and data it contains) through an `OSISolverInterface`. For the sake of
32simplicity, we will refer to the `OsiSolverInterface` as "the solver" in
33this document, rather than "the standard application programming
34interface to the solver." We hope any confusion caused by blurring this
35distinction will be mitigated by the shorter sentences.
36
37In summary, readers should have the following prerequisites:
38
39  - C++ knowledge,
40  - LP and MIP fundamentals, and
41  - OSI familiarity.
42
43Unless otherwise stated, we will assume the problem being optimized is a
44minimization problem. The terms "model" and "problem" are used
45synonymously.
46
47## Branch-and-Cut Overview
48
49Before examining CBC in more detail, we tersely describe the basic
50branch-and-cut algorithm by way of example, (which should really be
51called branch-and-cut-and-bound) and show the major C++ class(es) in CBC
52related to each step. The major CBC classes, labeled (A) through (F),
53are described in the table below.
54
55- Step 1. (Bound) Given a MIP model to minimize where some variables must
56  take on integer values (e.g., 0, 1, or 2), relax the integrality
57  requirements (e.g., consider each "integer" variable to be continuous
58  with a lower bound of 0.0 and an upper bound of 2.0). Solve the
59  resulting linear model with an LP solver to obtain a lower bound on the
60  MIP's objective function value. If the optimal LP solution has integer
61  values for the MIP's integer variables, we are finished. Any
62  MIP-feasible solution provides an upper bound on the objective value.
63  The upper bound equals the lower bound; the solution is optimal.
64
65- Step 2. (Branch) Otherwise, there exists an "integer" variable with a
66  non-integral value. Choose one non-integral variable (e.g., with value
67  1.3) (A)(B) and branch. Create two nodes, one with the branching
68  variable having an upper bound of 1.0, and the other with the branching
69  variable having a lower bound of 2.0. Add the two nodes to the search
70  tree.
71
72  While (search tree is not empty)
73  - Step 3. (Choose Node) Pick a node off the tree (C)(D)
74  - Step 4. (Re-optimize LP) Create an LP relaxation and solve.
75  - Step 5. (Bound) Interrogate the optimal LP solution, and try to prune
76    the node by one of the following.
77    - LP is infeasible, prune the node.
78    - Else, the optimal LP solution value of the node exceeds the current
79      upper bound, prune the node.
80    - Else, the optimal LP solution of the node does not exceed the
81      current upper bound and the solution is feasible to the MIP. Update
82      the upper bound, and the best known MIP solution, and prune the node
83      by optimality.
84  - Step 6. (Branch) If we were unable to prune the node, then branch.
85    Choose one non-integral variable to branch on (A)(B). Create two nodes
86    and add them to the search tree.
87
88This is the outline of a "branch-and-bound" algorithm. If in optimizing
89the linear programs, we use cuts to tighten the LP relaxations (E)(F),
90then we have a "branch-and-cut" algorithm. (Note, if cuts are only used
91in Step 1, the method is called a "cut-and-branch"
92algorithm.)
93
94| Note | Class name         | Description                                                                                                                                                                                                                                                             |
95| ---- | ------------------ | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
96| (A)  | `CbcBranch...`     | 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.                                                                   |
97| (B)  | `CbcNode`          | This class decides which variable/entity to branch on next. Even advanced users will probably only interact with this class by setting `CbcModel` parameters ( e.g., priorities).                                                                                       |
98| (C)  | `CbcTree`          | 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.                                                                                          |
99| (D)  | `CbcCompare...`    | 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.                                                                                   |
100| (E)  | `CglCutGenerators` | 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. |
101| (F)  | `CbcHeuristics`    | 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.                                                                                   |
102
103There are a number of resources available to help new CBC users get
104started. This document is designed to be used in conjunction with the
105files in the Samples subdirectory of the main CBC directory
106(`Cbc/examples`). The Samples illustrate how to use CBC and may also
107serve as useful starting points for user projects. In the event that
108either this document or the available [Doxygen content](http://www.coin-or.org/Doxygen/Cbc)
109conflicts with the observed behavior of the source code, the comments in
110the Cbc header files are the ultimate reference.
Note: See TracBrowser for help on using the repository browser.