Cones of nonnegative quadratic pseudo-boolean functions

Numerous combinatorial optimization problems can be formulated as the minimization of a quadratic pseudo-Boolean function in n variables, which on its own turn is equivalent with a linear programming problem over the so called Boolean Quadric Polytope (BQ) in (Formula presented.) dimension (Padberg, 1989). This polytope is very well studied, still we know in fact very little about its structure and its facets (complete description is known only for n ≤ 6.) It is known and easy to see that the facets of BQ are in a one to one correspondence with the extremal rays of the cone of nonnegative quadratic pseudo-Boolean functions. Consequently, subcones of this cone correspond to polyhedral relaxations of BQ. Several such relaxations were introduced in the past with several open question remaining regarding the relation of these relaxations. The aim of this short note is to fill in some of these gaps and bring more clarity to the relations between the corresponding polyhedral hierarchies. Our approach utilizes the above cited connection to the cone of nonnegative quadratic pseudo-Boolean functions and is rather algebraic.