We start with an initial integer formulation of the problem, and solve the linear relaxation.
Let's assume for semplicity that P is a polytope so that the linear problem is bounded. If the linear relaxation is infeasible, then S is empty and the method stops. Otherwise, we perform iteratively the following steps. If the current solution x* is not integer then we call up a procedure that solves the separation problem and finds out one or more inequalities in L violated by x*. These inequalities are added to the current formulation and the new linear problem is solved.
Since the old solution x* is no longer feasible because of the constraints added at the last step, the new optimal solution is different from x*. The procedure stops when an integer solution is found.
Since the formulation at the last step is a relaxation of the integer problem, then the last optimal solution x* is an optimal solution of the integer problem.
This is a general scheme of a cutting plane algorithm. Let's now look at two particular families of valid inequalities for a general integer linear programming problem and how to solve the corresponding separation problem.