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