Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations

September, 2004
Report Number: 
671
Authors: 
M. J. Wainwright and M. I. Jordan
Abstract: 

The Sherali-Adams (SA) and Lasserre (LA) approaches are ``lift-and-project'' methods that generate nested sequences of linear and/or semidefinite relaxations of an arbitrary 0-1 polytope $P \subseteq [0,1]^n$. Although both procedures are known to terminate with an exact description of $P$ after $n$ steps, there are various open questions associated with characterizing, for particular problem classes, whether exactness is obtained at some step $s < n$. This paper provides sufficient conditions for exactness of these relaxations based on the hypergraph-theoretic notion of treewidth. More specifically, we relate the combinatorial structure of a given polynomial system to an underlying hypergraph. We prove that the complexity of assessing the global validity of moment sequences, and hence the tightness of the SA and LA relaxations, is determined by the \emph{treewidth} of this hypergraph. We provide some examples to illustrate this characterization.

PDF File: 
Postscript File: