A pseudo-Boolean consensus approach to nonlinear 01 optimization
It is proved that any pseudo-Boolean function f f can be represented as f ( x ) ? z + ? ( x , x ? ) , where z is the minimum of f f and ? ? is a polynomial with positive coefficients in the original variables xi x i 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.
consensus nonlinear binary optimization boolean algebra