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.