• What is branch, cut, and price?
• What does a branch, cut, and price framework do?
• What software is available for branch, cut, and price?
• What makes branch, cut, and price different from branch and bound?
• Should I just use a generic MILP solver?
• What is SYMPHONY?
• What applications are available?
• What is open source software?
• What is COIN-OR?

Branch, cut, and price (BCP) is an LP-based branch and bound technique for solving mixed integer linear programs (MILPs). In BCP, both cuts and variables are generated dynamically throughout the search tree, allowing the solution of large-scale instances.

Because branch, cut, and price depends inherently on problem-specific techniques, many implementations are customized for a particular problem setting. Numerous such specialized codes have been developed, for instance CONCORDE, a TSP solver.

Frameworks, on the other hand, implement just the generic parts of the algorithm, leaving hooks for the user to insert customized application-specific methods where needed. This allows quick development of customized code without wasted effort.

SYMPHONY is a framework for implementing branch and cut algorithms in both sequential and parallel environments (distributed- or shared-memory). There are also a numbner of other branch, cut, and price (BCP) frameworks available. For a short list of other BCP software, click here

A BCP framework implements just the generic parts of the BCP algorithm, leaving hooks for the user to insert customized application-specific methods where desired. This allows quick development of customized code without wasted effort.

Branch, cut, and price is an implementation of branch and bound in which linear programming is used to derive valid bounds during construction of the search tree. Problem-specific cutting planes are used to strengthen the linear programming relaxations used for bounding. This makes it a much more powerful method than branch and bound alone.

Although many excellent generic MILP solvers employing a version of the branch and cut algorithm are now available, most are not as flexible as framework like SYMPHONY, which is designed to allow the user to insert specialized methods that take advantage of problem structure. It is not possible to solve many of the toughest discrete optimization problems without problem-specific modifications to the generic algorithm. In recent versions of commercial MILP solvers such as CPLEX, it has become possible to add problem-specific cuts and customize certain features, but frameworks such as SYMPHONY are more flexible and support a much wider range of options. If you do not need to develop a custom code, then you are probably better off with a commercial MILP solver. Of course, having access to the full source code is also a big advantage of SYMPHONY and other open-source alternatives.

Please click here to go to the home page for SYMPHONY.

Please click here to see a list of branch, cut, and price applications built with SYMPHONY.

Open-source software is software that is distributed under an open-source license. Open source license allow the user of the software certain rights, such as access to the source code and the ability to redistribute the software under certain conditions. The big advantage of open-source software is that the user has access to the inner workings and can participate directly in development efforts. This also allows development of highly specialized versions of the original code. For more information, visit the Open Source Initiative.

COIN-OR is the Computational Infrastructure for Operations Research project and is a consortium of researchers and practitioners from both academia and industry who support the development og open-source software tools for operations research. The project is run by the non-profit COIN-OR Foundation. The software available on this site is part of the COIN-OR software repository. All software available at this site uses COIN-OR's open-source license, called the Common Public License.