A pseudo-Boolean consensus approach to nonlinear 0–1 optimization

It is proved that any pseudo-Boolean function ff can be represented as f(x)≡z+φ(x,x̄), where z is the minimum of ff and φφ is a polynomial with positive coefficients in the original variables xixi and in their complements x̄i. A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions.