Fortunately, if we are interested in finding an optimal solution on S, or for optimization purposes, we do not need a complete linear description of P(S) but all we need to do is represent this polyhedron in the neighborhood of an optimal solution. In other words, we may solve the integer problem as soon as we are able to produce a relaxation Q of P(S), that is to say ,a polyhedron containing P(S), with the property that at least one of the optimal solutions of the integer problem is an optimal solution of the linear problem on Q.
As an example consider the same figure as in the previous slide. If we add to P the constraint corresponding to the green line we obtain a relaxation Q which contains P(S) properly since Q contains two blue vertices of P. Nevertheless, if we optimize the linear function cx on the polyhedron Q we get as an optimal solution the point x2 that belongs to S.
How are we to obtain such a relaxation? The idea is to iteratively construct it by adding new constraints to the initial formulation P of the problem in such a way that no feasible solution is lost and possibly large parts of P not contained in P(S) are cut off.