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

It is proved that any pseudo-Boolean function image can be represented as image, where z is the minimum of image and image is a polynomial with positive coefficients in the original variables image and in their complements image. 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.