Facets of the independent set polytope
type: Item
instance of: scholarly article
title: Facets of the independent set polytope
zbMATH Open document ID: 1060.90078
author: T. Easton
author: Kevin Hooker
author: Eva K. Lee
published in: Mathematical Programming. Series A. Series B
publication date: 2004-03-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 2055178
zbMATH Keywords: facet
zbMATH Keywords: independent set polytope
zbMATH Keywords: conflict hypergraphs
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
full work available at URL: s10107-003-0401-y
OpenAlex ID: W2012125315
DOI: 10.1007/S10107-003-0401-Y
description: scientific article; zbMATH DE number 2055178