Version 4 (modified by jpfasano, 16 years ago) (diff)

moved text from

Branch-Cut-Price Framework

Embedded documentation (Doxygen): BCP class descriptions




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



What is Branch-Cut-Price (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.

Who should use BCP?

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.

How is BCP parallelized?

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

Can BCP be used in a serial environment?

Yes. BCP contains a message passing module that mimics a parallel environment on a single processor.

What kind of LP solvers can be used with BCP?

BCP uses the OSI, which enables the use of any LP solver that OSI is interfaced with.

What are the main features of BCP?

Generalized branching objects, strong branching, reduced cost fixing, use of cut and variable pools, handling locally valid cuts, etc.

Can one use BCP as a general IP solver?

Not at the moment. When BCP is interfaced with CGL and CGL is well populated, BCP could be used as a general solver.

For what type of problems has BCP been used?

Multiple knapsack with color constraints(mkc), max-cut, and some proprietary projects.

What platforms does BCP run on?

BCP should run on any POSIX compatible unix (TM) platform. BCP has been tested on:

  • AIX V4.3 and V5.1 using g++ or Visual Age C++ (xlC) V5.1 or greater.
  • Linux using g++
  • Solaris (SunOS 5.6 and 5.8) using g++ or CC (SUNPRO_CC V6.2 or greater)
  • Windows using g++ under Cygwin environment
  • Mac OSX (a.k.a. Darwin) using g++

For all platforms above: when g++ is used at least V2.95.3 is needed. V3.2 and V3.3 works well. V3.0 is not recommended 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.

Is there any alternative to BCP?

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.