source: branches/gh-pages/ @ 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
  • Property svn:eol-style set to native
File size: 21.8 KB
1# The CBC Model Class
3## Overview
5The main class in CBC is `CbcModel`. The `CbcModel` class is where most
6of the parameter setting is done. The absolute minimum number of actions
7taken with `CbcModel` is two,
9  - `CbcModel(OsiSolverInterface & linearSolver)` as constructor, and
11  - `branchAndBound()` for solving the problem.
13## Simple Branch-and-Bound Example
15The first sample program shows how to perform simple branch-and-bound
16with CBC. This program is short enough to present in full. Most of the
17remaining examples will take the form of small code fragments. The
18complete code for all the examples in this Guide can be found in the CBC
19Samples directory, `Cbc/examples`.
22// Copyright (C) 2005, International Business Machines
23// Corporation and others.  All Rights Reserved.
25#include "CbcModel.hpp"
27// Using CLP as the solver
28#include "OsiClpSolverInterface.hpp"
30int main (int argc, const char *argv[])
32  OsiClpSolverInterface solver1;
34  // Read in example model in MPS file format
35  // and assert that it is a clean model
36  int numMpsReadErrors = solver1.readMps("../../Data/Sample/p0033.mps","");
37  assert(numMpsReadErrors==0);
39  // Pass the solver with the problem to be solved to CbcModel
40  CbcModel model(solver1);
42  // Do complete search
43  model.branchAndBound();
45  // Print the solution.  CbcModel clones the solver so we
46  //  need to get current copy from the CbcModel
47  int numberColumns = model.solver()->getNumCols();
49  const double * solution = model.solver()->getColSolution();
51  for (int iColumn=0;iColumn<numberColumns;iColumn++) {
52    double value=solution[iColumn];
53    if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn))
54      printf("%d has value %g\n",iColumn,value);
55   }
56  return 0;
60This program creates a `OsiClpSolverInterface` solver interface
61(i.e., `solver1`), and reads an MPS file. If there are no errors, the
62program passes the problem to `CbcModel` which solves the problem using
63the branch-and-bound algorithm. The part of the program which solves the
64problem is very small (one line!) but before that one line, the LP solver
65(i.e., `solver1`) had to be created and populated with the problem.
66After that one line, the results were printed out.
68## The Relationship Between OSI and CBC
70The above program illustrates the dependency
71of CBC on the `OsiSolverInterface` class. The constructor of `CbcModel`
72takes a pointer to an `OsiSolverInterface` (i.e., a solver). The
73`CbcModel` clones the solver, and uses its own instance of the solver.
74The `CbcModel`'s solver and the original solver (e.g., `solver1`) are
75not in sync unless the user synchronizes them. The user can always
76access the `CbcModel`'s solver through the `model()` method. To
77synchronize the two solvers, explicitly refreshing the original, e.g.,
80solver1 = model.solver();
83`CbcModel`'s method `solve()` returns a pointer to CBC's cloned solver.
85For convenience, many of the OSI methods to access problem data have
86identical method names in `CbcModel`. (It's just more convenient to type
87`model.getNumCols()` rather than `model.solver()->getNumCols()`). The
88`CbcModel` refreshes its solver at certain logical points during the
89algorithm. At these points, the information from the `CbcModel` `model`
90will match the information from the `model.solver()`. Elsewhere, the
91information may vary. For instance, the OSI method `getColSolution()`
92will contain the best solution so far, while the `CbcModel` method may
93not. In this case, it is safer to use `CbcModel::bestSolution()`.
95While all the OSI methods have equivalent methods
96in `CbcModel`, there are some OSI methods which do not. For example, if
97the program produced a lot of undesired output, one might add the line
103to reduce the output. There is no `setHintParam()` method in `CbcModel`.
105## Getting Solution Information
107Optimality can be checked through a call to `model.isProvenOptimal()`.
108Also available are `isProvenInfeasible()`, `isSolutionLimitReached()`,
109`isNodeLimitReached()` or the feared `isAbandoned()`. There is also
110`int status()` which returns 0 if finished (which includes the case
111when the algorithm is finished because it has been proved infeasible), 1
112if stopped by user, and 2 if difficulties arose.
114In addition to these `CbcModel` methods, solution values can be accessed
115via OSI methods. The OSI methods pick up the current solution in the
116`CBCModel`. The current solution will match the best solution found so
117far if called after `branchAndBound()` and a solution was
120| Purpose                    | Name                              | Notes                                                                                                                                                      |
121| -------------------------- | --------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------- |
122| Primal column solution     | `const double * getColSolution()` | The OSI method will return the best solution found thus far, unless none has been found. It is safer to use `CbcModel` version, `CbcModel::bestSolution()` |
123| Dual row solution          | `const double * getRowPrice()`    | Identical `CbcModel` version available, `CbcModel::getRowPrice()`.                                                                                         |
124| Primal row solution        | `const double * getRowActivity()` | Identical `CbcModel` version available, `CbcModel::getRowActivity()`.                                                                                      |
125| Dual column solution       | `const double * getReducedCost()` | Identical `CbcModel` version available, `CbcModel::gtReducedCost()`.                                                                                       |
126| Number of rows in model    | `int getNumRows()`                | Identical `CbcModel` version available, `CbcModel::getNumRows()`. Note: the number of rows can change due to cuts.                                         |
127| Number of columns in model | `int getNumCols()`                | Identical `CbcModel` version available, `CbcModel::getNumCols()`.                                                                                          |
129## Useful Set and Get Methods in `CbcModel`
131Most of the parameter setting in CBC is done through `CbcModel` methods.
132The most commonly used set and get methods are the following:
134| Method(s)                                                                                                                                                                                                                                             | Description                                                                                                                                                |
135| ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------- |
136| `bool setMaximumNodes(int value)` `int getMaximumNodes() const` `bool setMaximumSeconds(double value)` `double getMaximumSeconds()` `bool setMaximumSolutions(double value)` `double getMaximumSolutions() const`                                     | These set methods tell CBC to stop after a given number of nodes, seconds, or solutions is reached. The get methods return the corresponding values.       |
137| `bool setIntegerTolerance(double value) const` `double getIntegerTolerance() const`                                                                                                                                                                   | An integer variable is deemed to be at an integral value if it is no further than this `value` (tolerance) away.                                           |
138| `bool setAllowableGap(double value)` `double getAllowableGap() const` `bool setAllowablePercentageGap(double value)` `double getAllowablePercentageGap() const` `bool setAllowableFractionGap(double value)` `double getAllowableFractionGap() const` | `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. |
139| ` void setNumberStrong(double value)  ` ` int numberStrong() const  `                                                                                                                                                                                 | These methods set or get the maximum number of candidates at a node to be evaluated for strong branching.                                                  |
140| ` void setPrintFrequency(int value)  ` `int printFrequency() const`                                                                                                                                                                                   | Controls the number of nodes evaluated between status prints. Print frequency has a very slight overhead, if `value` is small.                             |
141| `int getNodeCount() const`                                                                                                                                                                                                                            | Returns number of nodes evaluated in the search.                                                                                                           |
142| `int numberRowsAtContinuous() const`                                                                                                                                                                                                                  | Returns number of rows at continuous                                                                                                                       |
143| `int  numberIntegers() const` `const int * integerVariable() const`                                                                                                                                                                                   | Returns number of integer variables and an array specifying them.                                                                                          |
144| `bool isBinary(int colIndex) const` `bool isContinuous(int colIndex) const` `bool isInteger(int colIndex) const`                                                                                                                                      | Returns information on variable `colIndex`. OSI methods can be used to set these attributes (before handing the model to `CbcModel`).                      |
145| `double getObjValue() const`                                                                                                                                                                                                                          | This method returns the best objective value so far.                                                                                                       |
146| `double getCurrentObjValue() const`                                                                                                                                                                                                                   | This method returns the current objective value.                                                                                                           |
147| `const double * getObjCoefficients() const`                                                                                                                                                                                                           | This method return the objective coefficients.                                                                                                             |
148| `const double * getRowLower() const` `const double * getRowUpper() const` `const double * getColLower() const` `const double * getColUpper() const`                                                                                                   | These methods return the lower and upper bounds on row and column activities.                                                                              |
149| `const CoinPackMatrix * getMatrixByRow() const`                                                                                                                                                                                                       | This method returns a pointer to a row copy of matrix stored as a `CoinPackedMatrix` which can be further examined.                                        |
150| `const CoinPackMatrix * getMatrixByCol() const`                                                                                                                                                                                                       | This method returns a pointer to a column copy of matrix stored as a `CoinPackedMatrix` which can be further examined.                                     |
151| `CoinBigIndex getNumElements() const` (`CoinBigIndex` is a `typedef` which in most cases is the same as `int`)                                                                                                                                        | Returns the number of nonzero elements in the problem matrix.                                                                                              |
152| `void setObjSense(double value)` `double getObjSense() const`                                                                                                                                                                                         | These methods set and get the objective sense. The parameter `value` should be +1 to minimize and -1 to maximize.                                          |
154## Impacting the Solution Process
156`CbcModel` is extremely flexible and customizable. The class structure
157of CBC is designed to make the most commonly desired customizations of
158branch-and-cut possible. These include:
160  - selecting the next node to consider in the search tree,
161  - determining which variable to branch on,
162  - using heuristics to generate MIP-feasible solutions quickly,
163  - including cut generation when solving the LP-relaxations, and
164  - invoking customized subproblem solvers.
166To enable this flexibility, `CbcModel` uses other classes in CBC (some
167of which are virtual and may have multiple instances). Not all classes
168are created equal. The two tables below list in alphabetical order the
169classes used by `CbcModel` that are of most interest and of least
172| Class name           | Description                                                                                                                                             | Notes                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
173| -------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
174| `CbcCompareBase`     | Controls which node on the tree is selected.                                                                                                            | The default is `CbcCompareDefault`. Other comparison classes in `CbcCompareActual.hpp` include `CbcCompareDepth` and `CbcCompareObjective`. Experimenting with these classes and creating new compare classes is easy.                                                                                                                                                                                                                                                                              |
175| `CbcCutGenerator`    | A wrapper for `CglCutGenerator` with additional data to control when the cut generator is invoked during the tree search.                               | Other than knowing how to add a cut generator to `CbcModel`, there is not much the average user needs to know about this class. However, sophisticated users can implement their own cut generators.                                                                                                                                                                                                                                                                                                |
176| `CbcHeuristic`       | Heuristic that attempts to generate valid MIP-solutions leading to good upper bounds.                                                                   | Specialized heuristics can dramatically improve branch-and-cut performance. As many different heuristics as desired can be used in CBC. Advanced users should consider implementing custom heuristics when tackling difficult problems.                                                                                                                                                                                                                                                             |
177| `CbcObject`          | 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`. |
178| `OsiSolverInterface` | Defines the LP solver being used and the LP model. Normally a pointer to the desired `OsiSolverInteface` is passed to `CbcModel` before branch and cut. | Virtual class. The user instantiates the solver interface of their choice, e.g., `OsiClpSolverInterface`.                                                                                                                                                                                                                                                                                                                                                                                           |
180There is not much about the following classes that the average user needs to know about.
182| Class name           | Description                                                                                                        | Notes                                                                                                                       |
183| -------------------- | ------------------------------------------------------------------------------------------------------------------ | --------------------------------------------------------------------------------------------------------------------------- |
184| `CbcBranchDecision`  | Used in choosing which variable to branch on, however, most of the work is done by the definitions in `CbcObject`. | Defaults to `CbcBranchDefaultDecision`.                                                                                     |
185| `CbcCountRowCut`     | Interface to `OsiRowCut`. It counts the usage so cuts can gracefully vanish.                                       | See `OsiRowCut` for more details.                                                                                           |
186| `CbcNode`            | Controls which variable/entity is selected to be branch on.                                                        | Controlled via `CbcModel` parameters. Information from `CbcNode` can be useful in creating customized node selection rules. |
187| `CbcNodeInfo`        | Contains data on bounds, basis, etc. for one node of the search tree.                                              | Header is located in `CbcNode.hpp`.                                                                                         |
188| `CbcTree`            | Defines how the search tree is stored.                                                                             | This class can be changed but it is not likely to be modified.                                                              |
189| `CoinMessageHandler` | Deals with message handling                                                                                        | The user can inherit from `CoinMessageHandler` to specialize message handling.                                              |
190| `CoinWarmStartBasis` | Basis representation to be used by solver                                                                          |                                                                                                                             |
Note: See TracBrowser for help on using the repository browser.