source: html/trunk/Cbc/ch01s04.html @ 559

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

word change

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.9 KB
1<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?>
2<html xmlns=""><head><title>
3Branch-and-Cut Overview
4</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="ch01.html" title="Chapter 1. &#10;    Introduction&#10;  "/><link rel="previous" href="ch01s03.html" title="Preliminaries"/><link rel="next" href="ch02.html" title="Chapter 2. &#10;   The CBC Model Class&#10;  "/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">
5Branch-and-Cut Overview
6</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch01s03.html">Prev</a> </td><th width="60%" align="center">Chapter 1. 
7    Introduction
8  </th><td width="20%" align="right"> <a accesskey="n" href="ch02.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="id2991765"/>
9Branch-and-Cut Overview
11  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 <a href="ch01s04.html#assClasses" title="Table 1.1. Associated Classes">Table 1.1</a>.
12 </p><p>
13Step 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.   
14 </p><p> 
15Step 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
16<sup>[<a id="id2991932" href="#ftn.id2991932">2</a>]</sup>
17nodes, 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.
18 </p><p>
19While (search tree is not empty) {
21   Step 3. (Choose Node) Pick a node off the tree (C)(D)
23   Step 4. (Re-optimize LP) Create an LP relaxation and solve.
25   Step 5. (Bound) Interrogate the optimal LP solution, and try to prune the node by one of the following.
26   </p><div class="itemizedlist"><ul type="disc"><li>
27    LP is infeasible, prune the node.
28    </li><li>
29    Else, the optimal LP solution value of the node exceeds the current upper bound, prune the node. 
30    </li><li>
31    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.         
32    </li></ul></div><p> 
34   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.
36 </p><p>     
37This 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.)
39  </p><div class="table"><a id="assClasses"/><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>
40    Note
41    </th><th>
42    Class name
43    </th><th>
44    Description
45    </th></tr></thead><tbody><tr><td align="left" valign="top">
46      (A)
47      </td><td align="left" valign="top"><tt class="classname">CbcBranch...</tt></td><td align="left" valign="top">
48      These classes define the nature of MIP's discontinuity.  The simplest discontinuity
49      is a variable which must take an integral value. Other types of discontinuities
50      exist, e.g., lot-sizing variables.
51      </td></tr><tr><td align="left" valign="top">
52      (B)
53      </td><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top">
54      This class decides which variable/entity to branch on next.
55      Even advanced users will probably only interact with this class by setting
56      <tt class="classname">CbcModel</tt> parameters ( e.g., priorities).
57      </td></tr><tr><td align="left" valign="top">
58      (C)
59      </td><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top">
60      All unsolved models can be thought of as being nodes on a tree where each
61      node (model) can branch two or more times. The interface with this class is helpful to know, but
62the user can pretty safely ignore the inner workings of this class.
63      </td></tr><tr><td align="left" valign="top">
64      (D)
65      </td><td align="left" valign="top"><tt class="classname">CbcCompare...</tt></td><td align="left" valign="top">
66      These classes are used in determine which of the unexplored nodes in the tree to consider next. These
67      classes are very small simple classes that can be tailored to suit the problem.
68      </td></tr><tr><td align="left" valign="top">
69      (E)
70      </td><td align="left" valign="top"><tt class="classname">CglCutGenerators</tt></td><td align="left" valign="top">
71      Any cut generator from CGL can be used in CBC. The cut generators are passed to CBC with parameters
72      which modify when each generator will be tried. All cut generators should be tried to
73      determine which are effective. Few users will write their own cut generators.
74      </td></tr><tr><td align="left" valign="top">
75      (F)
76      </td><td align="left" valign="top"><tt class="classname">CbcHeuristics</tt></td><td align="left" valign="top">
77      Heuristics are very important for obtaining valid solutions quickly.  Some
78      heuristics are available, but this is an area where it is useful and interesting to
79      write specialized ones.
80      </td></tr></tbody></table></div><p>
81  There are a number of resources available to help new CBC users get started.
82  This document is designed to be used in conjunction with the files in the
83  Samples subdirectory of the main CBC directory (<tt class="filename">COIN/Cbc/Samples</tt>).
84  The Samples illustrate how to use CBC and may also serve as useful starting points
85  for user projects.  In the event that either this document or the available
86  <a href="apb.html" title="Appendix B. Doxygen">Doxygen content</a> conflicts with the observed
87  behavior of the source code, the comments in the header files, found in
88  <tt class="filename">COIN/Cbc/include</tt>, are the ultimate reference.
89  </p><div class="footnotes"><br/><hr width="100" align="left"/><div class="footnote"><p><sup>[<a id="ftn.id2991932" href="#id2991932">2</a>] </sup>
90The current implementation of CBC allow two branches to be created. More general number of branches could be implemented.
91</p></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch01s03.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch01.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch02.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Preliminaries </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 2. 
92   The CBC Model Class
93  </td></tr></table></div></body></html>
Note: See TracBrowser for help on using the repository browser.