Branch and cut

Branch and cut is a method of combinatorial optimization for solving integer linear programs, which are linear programming problems in which some or all of the unknowns must take integer values. It runs a branch and bound search and uses cutting planes to tighten the linear programming relaxations. The method first solves the linear program without the integer constraint using the simplex algorithm. If the optimal solution gives a fractional value to a variable that should be an integer, a cutting plane procedure may find extra linear constraints that every feasible integer point satisfies but the current fractional solution violates, and these are added so that the next solve gives a less fractional answer. Branch and bound then splits the problem into restricted versions, usually two, and the process repeats, with fractional relaxation values serving as upper bounds and integral solutions as lower bounds so that nodes can be pruned. Cuts generated along the way may be global, valid for every feasible integer solution, or local to one branch. Branching strategies include most infeasible, pseudo cost and strong branching. If cuts are used only to tighten the initial relaxation the method is called cut and branch.