Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?

Question

I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf

One of the steps is to transform the inequalities of the original optimization problem (in an LP formulation for example) into equalities by adding a slack variable. In the example below (taken from page 17) is quite trivial how the bound was found to be 7, assuming x1 = x2 = 0 and x3 = 1, which is the "worst case" or the "furthest" we can be from 6 in the right hand side.

==============================================================

On the other hand, in page 25 there's another example which is making me a bit puzzled:

I'm failing to understand why 3 and 6 were chosen as the bounds here.

For example, for the first constraint, why isn't the bound 7? (assuming x1=x2=x3=x4=x5=0)

As for the third constraint, why isn't the bound 11? (assuming x1=x2=x3=x4=x5=1, so we'd have -16 + s <= -5)

Any help will be much appreciated! Maybe there's something obvious which I haven't realized :)

Answer 1

According to the equality constraint (the equal to 4 one), at least two of the $x_{?}$ are 1. Therefore, the slack for the 1st constraint is at most 3.

According to the equality constraint, the worst case is $x_1$, $x_4$, $x_5$ are 1 while other xs are 0. The slack is 6 in that case for the 3rd constraint.

Alternatively, we can approximate the bound of the slacks by noticing that the coefficients in each inequality constraint are all bigger than the coefficients in the equality constraint. Therefore we can at least subtract 4 from the bound of the slacks of the inequality constraints. 7 - 4 = 3 and 11 - 4 = 7 (ok, that is not 6).