This paper is an introduction to the Branch-and-Cut-and-Price (BCP) software available in the COIN repository [1]. Its scope is rather limited as its goal is to allow a new user to develop quickly his first application. The perspective is from a user point of view, skipping implementation details and options that are irrelevant for developing a simple application (i.e. ``the less I know about BCP, the better''). In particular, it focuses only on setting up a Branch-and-Cut algorithm, as adding the column generation process should not be too difficult once the Branch-and-Cut part is understood and set up.
All parts of the example were written for illustration purposes and were chosen to be mathematically as simple as possible. No claim is made regarding the efficiency or style of the code of the examples. Some operations could be done more efficiently by using additional features of BCP, at the cost of clarity. Learning how to use additional features and facilities of BCP can be done later on.
The reader is assumed to be familiar with the Branch-and-Cut process and its standard terminology. (An excellent introduction can be found in [4,6,7,8].) Basic knowledge of C++ is also required.
The code of the example BAC is based on the example BranchAndCut written by L. Ladányi and available in the COIN repository. These two examples complete each other, BAC illustrating the customization of the branching and the generation of the initial LP directly in the code while BranchAndCut shows how to use the predefined cut generators and how to define parameters. The structure of the two examples is quite similar and a new user is probably better of studying first the BAC example and then move on to the BranchAndCut example. Other examples are available in the COIN repository: Cgl1 and Cgl2 (illustrate the use of cut generators), MaxCut (a very efficient Branch-and-Cut code for solving Maximum Cut problems) [3], Mkc (a Branch-and-Price code for solving Multiple Knapsack with Color problems) [5], VolLp and Volume-LP (volume algorithm for solving LPs), and VolUfl (approximate solution of Uncapacited Facility Location problems).
This document can be read without knowledge of the BAC code itself, but it is probably better to have access to the code while reading. Additional information is available in the repository, under the ``Documentation'' heading. Particularly useful is the Doxygen documentation listing the BCP classes (link ``BCP class description'') [2], a convenient HTML interface to the BCP code.
Section 2 describes the integer linear problem solved in the example. Section 3 gives a general overview of BCP and other packages. Section 4 covers the installation, compilation and compilation flags of the example. Section 5 lists two data structures defined in BCP that are used in the example: vectors and matrices. Section 6 describes the three types of BCP variables and constraints. Section 7 covers the three main classes of the example: the class BB_prob (description of the problem), BB_TM (tree manager) and BB_LP (operations at the nodes of the tree). Finally, Section 8 discusses briefly the parameter file for BCP.
The description in this paper corresponds to the code available on the COIN repository on May 8, 2003. Since BCP is continuously in development, there is no guarantee that all details of the description will be accurate, even in a near future. The paper will hopefully be kept up to date and its most recent version will be available in the COIN repository.
Questions or bugs related to BCP or COIN in general should be directed to the bugs reporting site of the COIN repository (see FAQs), and other mailing lists available there. Questions or bugs related specifically to the BAC example should be directed to
fmargot@ms.uky.edu .