Cutting-plane method
The cutting-plane method by Gomory is a procedure used to find integer solutions of a linear program.
It works by solving the non-integer linear program, then testing if the optimum found is also an integer solution. If this is not the case, a new restriction is added that cuts off the non-integer solution but does not cut off any integer points of the feasible region. This is repeated until an optimal integer solution is found.
Interpreted geometrically, a restriction is equivalent to an oriented hyperplane, allowing only solutions on one side of the plane.
See also
Categories: Mathematics stubs