 (JF 04/01/05) The COINOR Branch and Cut code
+ The COINOR Branch and Cut code
is designed to be a high quality mixed integer code provided under the terms of the
Common Public License.
CBC is written in C++, and is primarily intended to be used as a callable
library (though a rudimentary standalone executable exists).
 The first documented release was .90.0 The current release is version .90.0.

Q:.
+ The first documented release was .90.0 The current release is version .90.0. (JF 04/01/05)
+
 (JF 04/01/05) If you can see this you have the best there is:)
+ If you can see this you have the best there is:)
Also available is a list of
CBC class descriptions generated
 by Doxygen.

 (JF 04/01/05) People from all around the world are already helping. There are
 probably ten people who are do not always post to discussions but are constantly
+ People from all around the world are already helping. There are
+ probably ten people who do not always post to the discussion mail list but are constantly
"improving" the code by demanding performance or bug fixes or enhancements. And there
 are others posting questions to discussion groups.

Fixed typos caught by Cole Smith, editor of the INFORMS Tutorial Book, and added place holders for needstobewritten sections, e.g., Using CGL with CBC.
Revision 0.2
May 2, 2005
RLH
Book chapter for CBC Tutorial at INFORMS 2005 annual meeting. Reorganized the content. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.
Revision 0.1
April 1, 2005
JF
First draft. The CBC documentation uses the DocBook CLP documentation created by David de la Nuez.
The COIN
 ^{[1]}
+ ^{[1]}
Branch and Cut solver (CBC) is an opensource mixedinteger program (MIP) solver written in C++. CBC is intended to be used primarily as a callable library to create customized branchandcut solvers. A basic, standalone executable version is also available. CBC is an active opensource project led by John Forrest at www.coinor.org.

+
Prerequisites
@@ 90,25 +90,23 @@
objectoriented programming terminology, and familiarity with the fundamental concepts of
 linear programming and
+ linear programming (LP) and
 mixed integer programming.
+ mixed integer programming (MIP).
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 CoinFactorization. This document assumes basic familiarity with OSI and CGL.
+CBC relies on other parts of the COIN repository. CBC needs a LP solver and relies on 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 CoinFactorization. This document assumes basic familiarity with OSI and CGL.
Technically speaking, CBC assesses the solver (and sometime the model and data it contains) through an OSISolverInterface. For the sake of simplicity, we will refer to the OsiSolverInterface 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.
+Technically speaking, CBC accesses the solver (and sometime the model and data it contains) through an OSISolverInterface. For the sake of simplicity, we will refer to the OsiSolverInterface 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.

+
In summary, readers should have the following prerequisites:

 C++ knowledge,

 LP and MIP fundamentals, and

 OSI familiarity.


Unless otherwise stated, we will assume the problem being optimized is a minimization problem. The terms "model" and "problem" are used synonymously.

+
C++ knowledge,
LP and MIP fundamentals, and
OSI familiarity.
+
Preliminaries
+
Unless otherwise stated, the problem being optimized is a minimization problem.
The terms "model" and "problem" are used synonymously.
Notation: We use the convention of appending an underscore to
+ a variable in order to distinguish member data of a class.
The Cbc Samples directory, COIN/Cbc/Samples
+ contains the source code for the examples in the Guide.
The sample code in the Guide is written for illustrative
+ purposes of the CBC concepts and usage. The sample code is not
+ necessarily written for performance.
+
BranchandCut Overview
@@ 117,5 +115,7 @@
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 MIPfeasible solution provides an upper bound on the objective value. The upper bound equals the lower bound; the solution is optimal.
Step 2. (Branch) Otherwise, there exists an "integer" variable with a nonintegral value. Choose one nonintegral 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.
+Step 2. (Branch) Otherwise, there exists an "integer" variable with a nonintegral value. Choose one nonintegral variable (e.g., with value 1.3) (A)(B) and branch. Create two
+^{[2]}
+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.
While (search tree is not empty) {
@@ 137,6 +137,5 @@
}
This is the outline of a "branchandbound" algorithm. If in optimizing the linear programs, we use cuts to tighten the LP relaxations (E)(F), then we have a "branchandcut" algorithm. (Note, if cuts are only used in Step 1, the method is called a "cutandbranch" algorithm.)

+This is the outline of a "branchandbound" algorithm. If in optimizing the linear programs, we use cuts to tighten the LP relaxations (E)(F), then we have a "branchandcut" algorithm. (Note, if cuts are only used in Step 1, the method is called a "cutandbranch" algorithm.)
TableÂ 1.1.Â Associated Classes
@@ 162,6 +161,6 @@
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.
+ node (model) can branch two or more times. The interface with this class is helpful to know, but
+the user can pretty safely ignore the inner workings of this class.
(D)
@@ 190,7 +189,9 @@
behavior of the source code, the comments in the header files, found in
COIN/Cbc/include, are the ultimate reference.

^{[1] }
+
^{[1] }
The complete acronym is "COINOR" 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".

ChapterÂ 2.Â
+
^{[2] }
+The current implementation of CBC allow two branches to be created. More general number of branches could be implemented.
+
The program in ExampleÂ 2.1 illustrates the dependency of CBC on
 the OsiSolverInterface class. The constructor of CbcModel takes a pointer to an OsiSolverInterface (i.e., a solver). The CbcModel clones the solver, and uses its own instance of the solver. The CbcModel's solver and the original solver (e.g., solver1) are not in sync unless the user synchronizes them. The user can always access the CbcModel's solver through the model() method. To synchronize the two solvers, explicitly refreshing the original, e.g.,
+ the OsiSolverInterface class. The constructor of CbcModel takes a pointer to an OsiSolverInterface (i.e., a solver). The CbcModel clones the solver, and uses its own instance of the solver. The CbcModel's solver and the original solver (e.g., solver1) are not in sync unless the user synchronizes them. The user can always access the CbcModel's solver through the model() class. To synchronize the two solvers, explicitly refreshing the original, e.g.,
solver1 = model.solver();
CbcModel's method solve() returns a pointer to CBC's cloned solver.
+CbcModel's method solver() returns a pointer to CBC's cloned solver.
For convenience, many of the OSI methods to access problem data have identical method names in CbcModel. (It's just more convenient to type model.getNumCols() rather than model.solver()>getNumCols()). The CbcModel refreshes its solver at certain logical points during the algorithm. At these points, the information from the CbcModelmodel will match the information from the model.solver(). Elsewhere, the information may vary. For instance, the OSI method getColSolution() will contain the best solution so far, while the CbcModel method may not. In this case, it is safer to use CbcModel::bestSolution().
+For convenience, many of the OSI methods to access problem data have identical method names in CbcModel. (It's just more convenient to type model.getNumCols() rather than model.solver()>getNumCols()). The CbcModel refreshes its solver at certain logical points during the algorithm. At these points, the information from the CbcModelmodel will match the information from the model.solver(). Elsewhere, the information may vary. For instance, the method CbcModel::bestSolution() will contain the best solution so far, the OSI method getColSolution() may not. In this case, it is safer to use CbcModel::bestSolution().
While all the OSI methods used in minimum.cpp have equivalent methods in CbcModel, there are some OSI methods which do not. For example, if the program produced a lot of undesired output, one might add the line
@@ 292,5 +293,5 @@
In addition to these CbcModel methods, solution values can be accessed via OSI methods. The OSI methods pick up the current solution in the CBCModel. The current solution will match the best solution found so far if called after branchAndBound() and a solution was found.

TableÂ 2.1.Â
+
TableÂ 2.1.Â
Methods for Getting Solution Information from OSI
CbcModel returns if the gap between the best known solution and the best
possible solution is less than this value, or as a percentage, or a fraction.

These methods set or get the maximum number of candidates at a node to
be evaluated for strong branching.
@@ 347,5 +349,6 @@
Returns number of nodes evaluated in the search.
intÂ numberRowsAtContinuous() const
 Returns number of rows at continuous
int Â numberIntegers() const const intÂ *Â integerVariable() const
+ Returns number of rows in the problem when handed to the solver (i.e., before cuts where added). Commonly used in implementing heuristics.
+
int Â numberIntegers() const const intÂ *Â integerVariable() const
Returns number of integer variables and an array specifying them.
These methods set and get the objective sense. The parameter
value should be +1 to minimize and 1 to maximize.

^{[a] }
+
^{[a] }
+This methods (and some of the other) do not follow the "get" convention. The convention has changed over time and there are still some inconsistencies to be cleaned up.
+
^{[b] }CoinBigIndex is a typedef which in
most cases is the same as int.
@@ 392,5 +397,5 @@
To enable this flexibility, CbcModel uses other classes in CBC (some of which are virtual and may have multiple instances). Not all classes are created equal. The two tables below list in alphabetical order the classes used by CbcModel that are of most interest and of least interest.

TableÂ 2.3.Â Classes Used by CbcModel  Most Useful
+
TableÂ 2.3.Â Classes Used by CbcModel  Most Useful
Class name
@@ 411,5 +416,5 @@
Defines what it means for a variable to be satisfied. Used in branching.
 Virtual class. CBC's concept of branching is based on the idea of an "object". An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparsion of the effect of branching. Instances of objects include CbcSimpleInteger, CbcSimpleIntegerPseudoCosts, CbcClique, CbcSOS (type 1 and 2), CbcFollowOn, and CbcLotsize.
+ Virtual class. CBC's concept of branching is based on the idea of an "object". An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparison of the effect of branching. Instances of objects include CbcSimpleInteger, CbcSimpleIntegerPseudoCosts, CbcClique, CbcSOS (type 1 and 2), CbcFollowOn, and CbcLotsize.
OsiSolverInterface
Defines the LP solver being used and the LP model. Normally
@@ 452,5 +457,7 @@
Selecting the Next Node in the Search Tree
 The order in which the nodes of the search tree are explored can strongly influence the performance of branchandcut algorithms. CBC give users complete control over the search order. The search order is controlled via the CbcCompare... class. CBC provides an abstract base class, CbcCompareBase, and several commonly used instances which are described in TableÂ 3.1.
+ The order in which the nodes of the search tree are explored can strongly influence the performance of branchandcut algorithms. CBC give users complete control over the search order, including the ability to dynamically change the node selection logic as the search progresses. The search order is controlled via the CbcCompare... class, and its method test(). Dynamic changes can be made whenever
+
a new solution is found  by customizing the method newSolution(), or
every 1000 nodes  by customizing the method every1000Nodes().
+CBC provides an abstract base class, CbcCompareBase, and implementations of several commonly used node selection strategies as Compare Classes, see TableÂ 3.1.
TableÂ 3.1.Â Compare Classes Provided
Class name
@@ 469,11 +476,9 @@
been found. It then use estimates that are designed to give a slightly better solution.
If a reasonable number of nodes have been explored (or a reasonable number of
 solutions found), then this class will adopt a breadthfirst search (i.e., making a comparison based strictly on objective function values) unless the tree is very large when it will revert to depthfirst search. A better description of CbcCompareUser is given below.
+ solutions found), then this class will adopt a breadthfirst search (i.e., making a comparison based strictly on objective function values) unless the tree is very large, in which case it will revert to depthfirst search. A better description of CbcCompareUser is given below.
CbcCompareEstimate
 When pseudo costs are invoked, they can be used to guess a solution. This class uses the guessed solution.
+ When pseudo costs are invoked, CBC uses the psuedo costs to guess a solution. This class uses the guessed solution.
 It is relatively simple for an experienced user to create new compare class instances. The code in ExampleÂ 3.1 describes how to build a new comparison class and the reasoning behind it. The complete source can be found in CbcCompareUser.hpp and CbcCompareUser.cpp, located in the CBC Samples directory. See ChapterÂ 7,
More Samples
. The key method in CbcCompare is bool test(CbcNode* x, CbcNode* y)) which returns true if node y is preferred over node x. In the test() method, information from CbcNode can easily be used. TableÂ 3.2 list some commonly used methods to access information at a node.
+ It is relatively simple for a user to create a customized node selection by creating a new compare class instances. The code in ExampleÂ 3.1 describes how to build a new comparison class and the reasoning behind it. The complete source can be found in CbcCompareUser.hpp and CbcCompareUser.cpp, located in the CBC Samples directory. Besides the constructor, the only method the user must implement in CbcCompare is bool test(CbcNode* x, CbcNode* y)) which returns true if node y is preferred over node x. In the test() method, information from CbcNode can easily be used. TableÂ 3.2 lists some commonly used methods to access information at a node.
TableÂ 3.2.Â Information Available from CbcNode
double objectiveValue() const
Value of objective at the node.
@@ 495,4 +500,5 @@
newSolution() is called whenever a solution is found and the method every1000Nodes() is called every 1000 nodes. When these methods are called, the user has the opportunity to modify the
behavior of test() by adjusting their common variables (e.g., weight_). Because CbcNode has a pointer to the model, the user can also influence the search through actions such as changing the maximum time CBC is allowed, once a solution has been found (e.g., CbcModel::setMaximumSeconds(double value)). In CbcCompareUser.cpp of the COIN/Cbc/Samples directory, four items of data are used.
+
1) The number of solutions found so far
@@ 504,5 +510,7 @@
4) A saved value of weight, saveWeight_ (for when weight is set back to 1.0 for special reason)
The full code for the CbcCompareUser::test() method is given in ExampleÂ 3.1.
+
+Initially, weight_ is 1.0 and the search is biased towards depth first. In
+fact, test() prefers y if y has fewer unsatisfied variables. In the case of a tie, test() prefers the node with the greater depth in tree. The full code for the CbcCompareUser::test() method is given in ExampleÂ 3.1.
ExampleÂ 3.1.Â CbcCompareUser::test()
@@ 530,6 +538,5 @@
Initially, weight_ is 1.0 and the search is biased towards depth first. In
fact, test() prefers y if y has fewer unsatisfied variables. In the case of a tie, test() prefers the node with the greater depth in tree. Once a solution is found, newSolution() is called. The method newSolution() interacts with test() by means of the variable weight_. If the solution was achieved by branching, a calculation is made to determine the cost per unsatisfied integer variable to go from the continuous solution to an integer solution. The variable weight_ is then set to aim at a slightly better solution. From then on, test() returns true if it seems that y will lead to a better solution than x. This source for newSolution() in given in ExampleÂ 3.2.
+CBC calls the method newSolution() after a new solution is found. The method newSolution() interacts with test() by means of the variable weight_. If the solution was achieved by branching, a calculation is made to determine the cost per unsatisfied integer variable to go from the continuous solution to an integer solution. The variable weight_ is then set to aim at a slightly better solution. From then on, test() returns true if it seems that y will lead to a better solution than x. This source for newSolution() in given in ExampleÂ 3.2.
ExampleÂ 3.2.Â CbcCompareUser::newSolution()
@@ 542,5 +549,7 @@
{
if (model>getSolutionCount()==model>getNumberHeuristicSolutions())
 return; // solution was found by rounding so ignore it.
+ return; // The number of solutions found by any means equals the
+ // number of solutions, so this solution was found by rounding.
+ // Ignore it.
// set weight_ to get close to this solution
@@ 548,6 +557,11 @@
(model>getObjValue()objectiveAtContinuous)/
((double) numberInfeasibilitiesAtContinuous);
 weight_ = 0.98*costPerInteger;
 saveWeight_=weight_;
+ weight_ = 0.98*costPerInteger; // this aims for a solution
+ // slightly better than known.
+ // why 0.98? why not?! Experiment yourself.
+ saveWeight_=weight_; // We're going to switching between depthfirst and breadthfirst
+ // branching strategies, depending on what we find in the tree.
+ // When doing depth first, we'll want to retrieve this weight.
+ // So, let's save it.
numberSolutions_++;
if (numberSolutions_>5)
@@ 558,16 +572,14 @@
As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been genereated, then weight_ is set to 0.0 leading to a breadthfirst search. Breadthfirst search can lead to an enormous tree. If the tree size is exceeds 10000, it may be desirable to return to a search biased towards depth first. Changing the behavior in this manner is done by the method every1000Nodes shown in ExampleÂ 3.3.
+As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been generated, then weight_ is set to 0.0 leading to a breadthfirst search. Breadthfirst search can lead to an enormous tree. If the tree size is exceeds 10000, it may be desirable to return to a search biased towards depth first. Changing the behavior in this manner is done by the method every1000Nodes shown in ExampleÂ 3.3.
ExampleÂ 3.3.Â CbcCompareUser::every1000Nodes()
// This allows the test() method to change behavior every so often
+// This allows the test() method to change behavior every 1000 nodes.
bool
CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
{
 if (numberNodes>10000)
+ if (numberNodes>10000)
weight_ =0.0; // compare nodes based on objective value
 else if (numberNodes==1000&&weight_==2.0)
 weight_=1.0; // Go to depth first
 // get size of tree
+ // get size of tree
treeSize_ = model>tree()>size();
if (treeSize_>10000) {
@@ 575,5 +587,6 @@
if (treeSize_>20000)
weight_=1.0;
 else if ((numberNodes%4000)!=0)
+ else if ((numberNodes%4000)!=0) // Flipflop between the strategies.
+ // Why 4000? Why not? Experiment yourself.
weight_=1.0;
else
@@ 594,20 +607,20 @@
current bounds. CBC provides an abstract base class CbcHeuristic and a rounding heuristic in CBC.
The greedy heuristic will leave all variables taking value one at this node of the
 tree at value one, and will initially set all other variable to value zero.
+ tree at value one, and will initially set all other variables to value zero.
All variables are then sorted in order of their cost
divided by the number of entries in rows which are not yet covered. (We may randomize that
value a bit so that ties will be broken in different ways on different runs of the heuristic.)
The best one is choosen, and set to one. The process is repeated. Because this is
 a set covering problem (i.e., all constraints are â¥), the heuristic is guaranteed to find a solution (but not necessarily an improved solution). The speed of the heuristic could be improved by just redoing those affected, but for illustrative purposes we will keep it simple.(The speed could also be improved if all elements are 1.0).
+ a set covering problem (i.e., all constraints are â¥), the heuristic is guaranteed to find a solution (but not necessarily an improved solution). The speed of the heuristic could be improved by just redoing those affected, but for illustrative purposes we will keep it simple. (The speed could also be improved if all elements are 1.0).
The key CbcHeuristic method is intÂ solution(double & solutionValue,
doubleÂ *Â betterSolution).
The solution() method returns 0 if no solution found, and returns 1 if a solution is found, in which case it fills in the objective value and primal solution. The code in CbcHeuristicGreedy.cpp is a little more complicated than this following example. For instance, the code here assumes all variables are integer. The important bit of data is a copy of the matrix (stored by column) before any cuts have been made. The data used are bounds, objective and the matrix plus two work arrays.

ExampleÂ 4.1.Â Data
+
ExampleÂ 4.1.Â Data
OsiSolverInterface * solver = model_>solver(); // Get solver from CbcModel
@@ 635,5 +648,5 @@
The newSolution is then initialized to the rounded down solution.

ExampleÂ 4.2.Â Initialize newSolution
+
ExampleÂ 4.2.Â Initialize newSolution
for (iColumn=0;iColumn<numberColumns;iColumn++) {
@@ 648,5 +661,5 @@
newSolution[iColumn]=value;
if (value) {
 double cost = direction * objective[iColumn];
+ double cost = objective[iColumn];
newSolutionValue += value*cost;
for (j=columnStart[iColumn];
@@ 661,6 +674,6 @@
At this point some row activities may be below their lower bound. To correct this infeasibility, the variable which is cheapest in reducing the sum of infeasibilities is found and updated, and the process repeats. This is a finite process. (Theimplementation could be faster, but is kept simple for illustrative purposes.)

ExampleÂ 4.3.Â Create Feasible newSolution from Initial newSolution
+At this point some row activities are below their lower bound. To correct the infeasibility, the variable which is cheapest in reducing the sum of infeasibilities is found and updated, and the process repeats. This is a finite process. (The implementation could be faster, but is kept simple for illustrative purposes.)
+
ExampleÂ 4.3.Â Create Feasible newSolution from Initial newSolution
while (true) {
@@ 708,6 +721,6 @@
A solution value of newSolution is compared to the best solution value. If newSolution is an improvement, its feasibility is validated.

ExampleÂ 4.4.Â Check Solution Quality of newSolution
+A solution value of newSolution is compared to the best solution value. If newSolution is an improvement, its feasibility is validated. We expect newSolution to be feasible, and are trapping for unexpected numerical errors.
+
ExampleÂ 4.4.Â Check Solution Quality of newSolution
returnCode=0; // 0 means no good solution
@@ 745,5 +758,11 @@
+CBC's concept of branching is based on the idea of an "object". An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparsion of the effect of branching. Instances of objects include.
+
CbcSimpleInteger,
CbcSimpleIntegerPseudoCosts,
CbcClique,
CbcSOS (type 1 and 2),
CbcFollowOn, and
CbcLotsize.
+In ChapterÂ 5,
+ Branching
+ , we give examples of how to use existing branching objects. (The next revision of this Guide should include an example of how to write your own branching object; Contributions of examples are welcome.)
+
Pseudo Cost Branching
If the user declares variables as integer but does no more, then CBC will treat them
@@ 751,5 +770,5 @@
it is assumed that if a variable is at 1.3 then the cost of branching that variable down will be 0.3 times the down pseudo cost and the cost of branching up would be 0.7 times the up pseudo cost. Pseudo costs can be used both for branching and for choosing a node.
The full code is in longthin.cpp located in the CBC Samples directory, see
 ChapterÂ 7,
+ ChapterÂ 8,
More Samples
.
@@ 801,10 +820,10 @@
The full sample code for followon brancing is in crew.cpp
located in the CBC Samples directory, see
 ChapterÂ 7,
+ ChapterÂ 8,
More Samples
). In this case, the simple integer
variables are left which may be necessary if other sorts of constraints exist. Followon branching rules are to be considered first, so the priorities are set to indicated the followon rules take precedence. Priority 1 is the highest priority.


ExampleÂ 5.2.Â CbcFollowOn
+variables are left which may be necessary if other sorts of constraints exist. Followon branching rules are to be considered first, so the priorities are set to indicate the followon rules take precedence. Priority 1 is the highest priority.
+
+
ExampleÂ 5.2.Â CbcFollowOn
int iColumn;
@@ 840,16 +859,19 @@
model.passInPriorities(&followPriority,true);

The method initialSolve is called a few times in CBC, and provides a convenient starting point. The modelPtr_ derives from OsiClpSolverInterface.

ExampleÂ 6.1.Â initialSolve()
+
ExampleÂ 7.1.Â initialSolve()
// modelPtr_ is of type ClpSimplex *
@@ 868,7 +890,7 @@
The resolve() method is more complicated than initialSolve(). The main pieces of data are a counter count_ which is incremented each solve and an integer array node_ which stores the last time
a variable was active in a solution. For the first few times, the normal Dual Simplex is called and
+a variable was active in a solution. For the first few solves, the normal Dual Simplex is called and
node_ array is updated.

ExampleÂ 6.2.Â First Few Solves
+
ExampleÂ 7.2.Â First Few Solves
if (count_<10) {
@@ 891,5 +913,5 @@
After the first few solves, only those variables which took part in a solution in the last so many
solves are used. As fast0507 is a set covering problem, any rows which are already covered can be taken out.

ExampleÂ 6.3.Â Create Small Problem
+
ExampleÂ 7.3.Â Create Small SubProblem
int * whichRow = new int[numberRows]; // Array to say which rows used
@@ 985,7 +1007,7 @@
If the variables cover the rows, then the problem is feasible (no cuts are being used). If the rows
were equality constraints, then this might not be the case. More work would be needed. After the solution, the reduct costs are checked. If any reduced costs are negative, the code goes back to the full problem and cleans up with Primal Simplex.

ExampleÂ 6.4.Â Check Optimal Solution
+If the variables cover the rows, then the problem is feasible (no cuts are being used). (If the rows
+were equality constraints, then this might not be the case. More work would be needed.) After the solution to the subproblem, the reduced costs of the full problem are checked. If the reduced cost of any variable not in the subproblem is negative, the code goes back to the full problem and cleans up with Primal Simplex.
+
ExampleÂ 7.4.Â Check Optimal Solution
temp>setDualObjectiveLimit(1.0e50); // Switch off dual cutoff as problem is restricted
@@ 1041,8 +1063,8 @@
The full code is in ClpQuadInterface.hpp and
ClpQuadInterface.cpp located in the CBC Samples directory, see
 ChapterÂ 7,
+ ChapterÂ 8,
More Samples
).

ExampleÂ 6.5.Â Solving a Quadratic MIP
+
ExampleÂ 7.5.Â Solving a Quadratic MIP
// save cutoff
@@ 1061,5 +1083,6 @@
ClpObjective * saveObjective = modelPtr_>objectiveAsObject();
modelPtr_>setObjectivePointer(quadraticObjective_);
 modelPtr_>primal();
+ modelPtr_>primal(); // Th model has a quadratic objective,
+ // so this invokes quadratic primal.
modelPtr_>setDualObjectiveLimit(cutoff);
if (modelPtr_>objectiveValue()>cutoff)
@@ 1067,7 +1090,9 @@
modelPtr_>setObjectivePointer(saveObjective);

ChapterÂ 7.Â
+
+Rather than implementing all the method from scratch, we based the quadratic solver ClpQuadInteface on the linear programming solver OsiClpSolverInterface. This is a convenient approach to take when prototyping ideas. After the merit of an idea is proven, the user can decide is a more serious implementation is warranted.
+
The CBC distribution includes a number of .cpp sample files.
Users are encouraged to use them as starting points for their own CBC projects.
@@ 1077,5 +1102,5 @@
by
make DRIVER=name
which produces an executable testit. Below is a list of
some of the most useful sample files with a short description for each file.

TableÂ 7.1.Â Basic Samples
+
TableÂ 8.1.Â Basic Samples
Source fileÂ Â Â Â Â Â Â
@@ 1092,5 +1117,5 @@
CbcHeuristicUser.cpp
with corresponding *.hpp files.

There are several log levels. Setting the log level to be i produces the log messages for level i and all levels less than i.
 Logging Level 0: Switches off all CBC messages, but one.
+ Log Level 0: Switches off all CBC messages, but one.
 Logging Level 1: The default.
+ Log Level 1: The default.
 Logging Level 2: Substantial amount of information, e.g., message 15 is generated once per node. Can be useful when the evaluation at each node is slow.
+ Log Level 2: Substantial amount of information, e.g., message 15 is generated once per node. Can be useful when the evaluation at each node is slow.
 Logging Level 3: Tremendous amount of information, e.g., multiple messages per node.

@@ 1335,10 +1360,10 @@
library (though a rudimentary standalone executable exists).
The first documented release was .90.0 The current release is version .90.0. (JF 04/01/05)

Q:.
+
Q:.
What are some of the features of CBC?
A:.
CBC allows the use of any CGL cuts and the use of heuristics and
specialized branching methods. (JF 04/01/05)

No. However its design is much more flexible so advanced users
will be able to tailor CBC to their needs. (JF 04/01/05)

Q:.
+
Q:.
When will version 1.0 of CBC be available?
A:.
It is expected that version 1.0 will be released in time for the 2005
INFORMS annual meeting. (JF 04/01/05)

Q:.
+
Q:.
What can the community do to help?
A:.
@@ 1400,3 +1425,3 @@
COIN/Cbc/Doc/html. The same can be done for
the COIN core, from the COIN/Coin directory.

AppendixÂ C.Â Revision History
Revision History
Revision 0.2
May 2, 2005
RLH
Book chapter for CBC Tutorial at INFORMS 2005 annual meeting. Reorganized the content. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.
Revision 0.1
April 1, 2005
JF
First draft. The CBC documenation uses the DocBook CLP documentation created by David de la Nuez.
+
AppendixÂ C.Â Revision History
Revision History
Revision 0.21
May 10, 2005
RLH
Fixed typos caught by Cole Smith, editor of the INFORMS Tutorial Book, and added place holders for needstobewritten sections, e.g., Using CGL with CBC.
Revision 0.2
May 2, 2005
RLH
Book chapter for CBC Tutorial at INFORMS 2005 annual meeting. Reorganized the content. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.
Revision 0.1
April 1, 2005
JF
First draft. The CBC documentation uses the DocBook CLP documentation created by David de la Nuez.
 These classes define what is the nature of discontinuity. The simplest
 are variables which must take an integral value but there others
 which will be described later e.g. lotsizing variables.

 (B)

 CbcNode

 This is the class that decides which variable/entity to branch on next.
 Even advanced users will probably only interact with this by setting
 CbcModel parameters e.g. priorities.

 (C)

 CbcTree

 All unsolved models can be thought of as being on a tree where each
 model can branch two or more times. The user should not need to be
 concerned with this class.

 (D)

 CbcCompare...

 All unsolved models are in a tree but which leaf do we choose. These
 classes are very small simple ones which can be tailored to suit the problem.

 (E)

 CglCutGenerators

 Any cut generator from Cgl can be given to the model to be used with parameters
 which modify when each generator will be tried. Few people will write their
 own cut generators but all should see which are effective.

 (F)

 CbcHeuristics

 Heuristics are very important for obtaining valid solutions quickly. Some
 are available but this is an area where it is useful and interesting to
 write specialized ones.

 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 (COIN/Cbc/Samples).
 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
 Doxygen content conflicts with the observed
 behavior of the source code, the comments in the header files, found in
 COIN/Cbc/include, are the ultimate reference.
