Facets of the independent set polytope (Q1424284)

The independent set polytope \(\text{ISP}= \{x\mid Ax\leq b,\, x\in\{0,1\}\}\) yields a hypergraph \(H\), containing \(V= \{1,\dots,n\}\) as vertices and a hyperedge \(eCV\) if and only if \(\sum_{j\in e} a_{ij}> b_i\) for some \(i\). If all edges have exactly \(k\) vertices, the hypergraph is an \(k\)-hypergraph \(H_k\). A hyperclique \(K_{m,k}\) in \(H_k\) is a set of \(m\) vertices such that the induced subhypergraph contains all \({m\choose k}\) edges. \(H_k\) of ISP is called a conflict \(k\)-hypergraph associated with ISP. The authors prove necessary and sufficient conditions for every nontrivial \(0-1\) facet-defining inequality in terms of maximal hypercliques of these conflict \(k\)-hypergraphs. In the special case of the knapsack polytope a short alternative proof to wellknown results of Balas, Hammer, Wolsey et.al. is given. Lifting is extended to get strong valid inequalities and back-lifting is introduced which often results in better cut coefficients. The authors propose a new branching scheme: A one-stage aggregate branching strategy is followed by a variable dichotomy branching, coupled with cutting planes which are induced by hyperclique inequalities. Computational results show, this approach may be useful for \(k\) near to \(0\) or \(n\). For arbitrary \(k\) the generation of the \(k\)-hypergraph may be NP-hard as well as finding maximal hypercliques, too.