Branch and Cut

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