Quadratic 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, that is, a mapping from $\{0,1\}^n$ to $\mathbf R$.
\emph{Nonlinear binary optimization problems} of the form \begin{equation}\label{eq:PBO} \min \{ f(x) : x \in \{0,1\}^n \},
\end{equation},
where $f$ is a pseudo-Boolean function expressed as a multilinear polynomial in its variables, are notoriously difficult.

For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a \emph{quadratization} of $f$ if $g(x,y)$ is a quadratic polynomial depending on $x$ and on $m$ \emph{auxiliary} binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $ for all $x \in \{0,1\}^n$.
By means of quadratizations, minimization of $f$ is reduced to minimization (over the extended set of variables) of the quadratic function $g(x,y)$. This is of practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and
much progress has been made in solving such problems exactly or heuristically.

This talk addresses two main types of questions. First, we want to determine the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function~$f$.
This question is rather natural since the complexity of minimizing the quadratic function $g(x,y)$ heavily depends (among other factors) on the number of binary variables~$(x,y)$.
We establish tight lower and upper bounds on the number of auxiliary variables needed in such a reformulation.

Next, we determine more precisely the number of auxiliary variables required by quadratizations of
\emph{symmetric} pseudo-Boolean functions $f(x)$, i.e., functions whose value only depends on
the number of variables equal to~$1$.