Cbc

Introduction

The COIN-OR Branch and Cut solver (CBC) is an open-source mixed-integer program (MIP) solver written in C++. CBC is intended to be used primarily as a callable library to create customized branch-and-cut solvers. A basic, stand-alone executable version is also available. CBC is an active open-source project led by John Forrest at www.coin-or.org.

Prerequisites

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 C++, including basic object-oriented programming terminology, and familiarity with the fundamental concepts of linear programming and mixed integer programming.

CBC relies other parts of the COIN-OR repository. CBC needs an LP solver and relies the COIN-OR 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-OR’s native linear program solver, CLP. For cut generators, CBC relies on the COIN-OR 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.

In summary, readers should have the following prerequisites:

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

Branch-and-Cut Overview

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 the table below.

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.)

Note Class name Description
(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.
(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).
(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.
(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.
(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.
(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.

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 (Cbc/examples). 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 Cbc header files are the ultimate reference.