The Binary Linearization Complexity of Pseudo-Boolean Functions

Matthias Walter

We consider the problem of linearizing a pseudo-Boolean function $f:\{0,1{\}}^n\to \mathbb{R}$ by means of $k$ Boolean functions. Such a linearization yields an integer linear pro…