Theoretical results pertaining to the independent set polytope PISP=conv{x ∈ {0, 1}n : Ax ≤ b} are presented. A conflict hypergraph is constructed based on the set of dependent sets which facilitates the examination of the facial structures of PISP. Necessary and sufficient conditions are provided for every non-trivial 0–1 facet-defining inequalities of PISP in terms of hypercliques. The relationship of hypercliques and some classes of knapsack facet-defining inequalities are briefly discussed. The notion of lifting is extended to the conflict hypergraph setting to obtain strong valid inequalities, and back-lifting is introduced to strengthen cut coefficients. Preliminary computational results are presented to illustrate the usefulness of the theoretical findings.
