Reformulations of nonlinear binary optimization problems

A {em pseudo-Boolean function}  is a real-valued function f(x)=f(x_1,x_2,ldots,x_n) of n binary variables. It is well-known  that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables.

emph{Nonlinear binary optimization problems}, or emph{pseudo-Boolean optimization} (PBO) emph{problems}, of the form 
min { f(x) : x in {0,1}^n },
where f(x) is a pseudo-Boolean polynomial,  have attracted the attention of numerous researchers for more than 50 years.  These problems are notoriously difficult, as they naturally encompass a broad variety of models such as maximum satisfiability, max cut, graph coloring, image restoration, and so on.

In this talk, I present recent results (obtained in collaboration with Martin Anthony, Endre Boros, Aritanan Gruber, and Elisabeth Rodriguez-Heck) regarding the size of reformulations of nonlinear PBO problems as quadratic PBO problems.

SLIDES