The Binary Boolean Optimization (BPO) problem aims at finding the maximal value that a rational polynomial P(x) can take when x is supposed to be a vector with 0 and 1 values. This non-linear optimization problem has recently received renewed attention. Current techniques for solving it either involve to solve a linear relaxation of the...