Let's now see which are the main properties of the sets P_j(K).
Evidently each of these sets is a polyhedron contained in K and containing the convex hull P(S) of the feasible solutions of the problem. Moreover, one can show that all the vertices of P_j(K) have their j-th component equal either to 0 or to 1. This immediately implies that each point of K having a fractional component x(j) does not belong to P_j(K). So we may try to solve the MIP problem with a cutting plane procedure that uses facets or at least valid inequalities of the polyhedra P_j(K) as cuts. To perform this idea first we have to derive the linear description of P_j(K) from that of K.
By definition each element of P_j(K) is the convex combination of two element x1 and x2 of K, the first having x(j) = o and the other x(j) = 1. This condition may be restated by saying that x belong to P_j(K) if there exist a1, a1 not negative and having sum 1 and y1 and y2 satisfying the folowing system of constraints.