Branch and cut

Branch and cut[1] is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values.

[2] Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations.

This description assumes the ILP is a maximization problem.

The method solves the linear program without the integer constraint using the regular simplex algorithm.

When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm may be used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution.

These inequalities may be added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional".

At this point, the branch and bound part of the algorithm is started.

The new linear programs are then solved using the simplex method and the process repeats.

Further, when solving the LP relaxations, additional cutting planes may be generated, which may be either global cuts, i.e., valid for all feasible integer solutions, or local cuts, meaning that they are satisfied by all solutions fulfilling the side constraints from the currently considered branch and bound subtree.

, in the optimal solution to the current LP relaxation and then adding the constraints