Branch and Cut

Download the paper, in pdf.

Author:

John E. Mitchell
mitchj at rpi.edu
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A

Feb 22, 2010. Revised May 12, 2010.

Abstract:

The performance of branch-and-bound methods for integer programming problems has been dramatically improved by incorporating cutting planes. The resulting technique is known as branch-and-cut. Cutting planes are inequalities that can be used to improve the linear programming relaxation of an integer programming problem. They are added as required, at the root node and also elsewhere in the tree. Problem specific cutting planes have been developed for many classes of problems. Recently, there has been great interest in improving and refining general classes of cutting planes, including for example Gomory cuts. Branch-and-cut algorithms can exploit parallel computers and multicore architecture in a natural way. Branch-and-cut has also been applied to mixed integer nonlinear programming problems.

Keywords: branch-and-cut, cutting planes, combinatorial optimization, integer programming

Accepted for publication in the Encyclopedia of Operations Research and Management Science.

Download the paper, in pdf.

Return to my list of papers.