A cutting plane algorithm for these kinds of problems is based on the following construction.
For each index j of a binary variable, we define two subsets of the polyhedron K, K(j,0) and K(j,1). They are the subsets containing all the elements of K having the j-th component equal to 0 and 1, respectively.
We then consider the convex hull Pj(K) of these two subsets.
For example in the figure we see a polyhedron K delimited by the black boundary. Assume that both x1 and x2 are binary variables and choose the first one. Then K(1,0) corresponds to the blue segment on the y-axis, while K(1,1) corresponds to the green segment in the figure. So the convex hull of these two disjoint sets is the polyhedron P1(K) delimited by these two segments and the red edges.
Let's now iterate this step taking Pi(K) as relaxation and considering a different variable of index not greater than p. The same construction carry to a polyhedron Pij. It can be shown that Pij is just the convex hull of the solution in K whose components of index i-th and j-th are 0 or 1. Then iterating the procedure for at most p step we obtain the convex hull of S, that is P(S).