The quick download and installation guide works in most cases if you don't have particular requirements.
For more detailed instructions, go to the CoinHelp page.
If you have installed Bcp according to the instructions in the quick download and installation guide you have built the code in the directory build.
There are two example codes installed in build/Bcp/examples: MCF and BAC. MCF is a multicommodity flow example
using column generation (the code is in development and might not be working yet). BAC is an example of a simple branch-and-cut application.
The INSTALL and README files in build/Bcp/examples/BAC
give pointers for installing and running the example, as well as
additional information for customizing the installation of BCP.
BCP is a parallel framework for implementing branch, cut, and price algorithms for solving mixed integer programs (MIPs). BCP provides the user with an object-oriented framework that can be used to develop an efficient problem class specific MIP solver without all the implementational effort. involved with implementing a branch and bound framework from scratch.
Because BCP is an open-source framework, users have the flexibility to customize any aspect of their BCP algorithm. BCP is appropriate for researchers who would like to experiment with different MIP formulations, new cut and/or variable generation techniques, branching strategies, etc., as well as power users who would like to solve intractable problems in a parallel environment.
You should read the InstallationAndGettingStarted document.
BCP processes the Branch-and-Bound search tree nodes in parallel by employing a master/slave model. BCP is designed for a distributed network via a message passing protocol (currently PVM, or a serial version).
Yes. BCP contains a message passing module that mimics a parallel environment on a single processor.
BCP uses the OSI, which enables the use of any LP solver that OSI is interfaced with.
Generalized branching objects, strong branching, reduced cost fixing, use of cut and variable pools, handling locally valid cuts, etc.
Not at the moment. When BCP is interfaced with CGL and CGL is well populated, BCP could be used as a general solver.
Multiple knapsack with color constraints(mkc), max-cut, and some proprietary projects.
BCP should run on any POSIX compatible unix (TM) platform. BCP has been tested on:
- AIX V4.3 or later using g++ or Visual Age C++ (xlC) V5.1 or greater.
- Linux (both 32 and 64 bit) using g++
- Solaris (SunOS 5.6 and 5.8) using g++ or CC (SUNPRO_CC V6.2 or greater)
- Windows using g++ under Cygwin or Msys environment
- Mac OSX (a.k.a. Darwin) using g++
- FreeBSD using g++
For all platforms above: when g++ is used at least V2.95.3 is needed, but nothing older than V3.3 is recommended (V3.0 is particularly bad as there are a number of bugs in that compiler).
At this time BCP does not compile on Windows with MS VC++ Version 6, because this compiler does not handle templated functions as BCP requires. Contributions to compile BCP on more platforms, especially on Windows perhaps with another compiler, are greatly appreciated.
SYMPHONY is a very similar open-source, parallel branch, cut, and price framework implemented in C. SYMPHONY compiles under MSVC++ and can also be compiled for shared memory architectures with an OpenMP compliant compiler. It has a more simplified interface and may be a better option for some users.
Embedded documentation (Doxygen): BCP class descriptions
Manuals:
- BCP manual (PostScript) (out of date---the most recent version is in CVS)
- BCP manual (PDF) (out of date---the most recent version is in CVS)
Presentations:
- Tutorial on BCP by Ted Ralphs can be accessed from the page on presentations from the 2004 CORS/INFORMS Joint Meeting in Banff
- BCP Tutorial given by Ted Ralphs at INFORMS 2003.
- A Library Hierarchy for Implementing Scalable Parallel Search Algorithms: A presentation on the new parallel search framework currently under development at INFORMS 2002 by Ted Ralphs, Laszlo Ladanyi, and Matthew Saltzman.
Publications:
- Francois Margot, BAC: A BCP based Branch-and-Cut Example. This paper is an introduction to the Branch-and-Cut-and-Price (BCP) software from the user perspective. It focuses on a simple example illustrating the basic operations used in a Branch-and-Cut:cuts and heuristic solutions generation, and customized branching.
- Laszlo Ladanyi, Jon Lee, Robin Lougee-Heimer, "Implementation of an exact algorithm for a cutting-stock problem using components of COIN-OR", submitted for publication, February 2003.
- Ted K. Ralphs, Laszlo Ladányi, and Matthew J. Saltzman, A Library Hierarchy for Implementing Scalable Parallel Search Algorithms, in review.
- Ted K. Ralphs, Laszlo Ladányi, and Matthew J. Saltzman, Parallel Branch, Cut, and Price for Large-scale Discrete Optimization, to appear in Mathematical Programming.
- Laszlo Ladányi, Ted K. Ralphs, and Matthew J. Saltzman, Implementing Scalable Parallel Search Algorithms for Data-intensive Applications, The Proceedings of the International Conference on Computational Science (2002), p. 592.
Examples:
- COIN-OR Tutorials page at the Lehigh Industrial and Systems Engineering Department.
- BAC: A BCP based Branch-and-Cut Example by Francois Margot.
- Help with COIN-OR: CoinHelp page.
- BCP html documentation
BCPmailing lists:- For general questions: BCP mailing list.
- For tickets: BCP-tickets mailing list.
- Reporting bugs:
- For download and installation: Go to the [WikiStart BuildTools Trac page] and post a new ticket. Follow these instructions.
- For a
BCPBug: Post a new ticket. Follow these instructions.
- COIN-OR home page