Cutting-Plane Method

The cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities called cuts, commonly used to find integer solutions to mixed integer linear programming problems and to solve general convex optimization problems that need not be differentiable. The use of cutting planes for mixed integer linear programming was introduced by Ralph E. Gomory. The method works by solving the non-integer linear relaxation of the given integer program, testing the resulting optimum for being an integer solution, and if it is not, finding a linear inequality, the cut, that separates that optimum from the convex hull of the true feasible set and adding it to the relaxed program; this process repeats until an optimal integer solution is found.