When there are linear constraints, interval arithmetic (like the one used in FBBT) can be taken one step further.
Take the linear constraint \(-10x_1-x_2 \leq -6\) for \(x_2 \in [1,4]\) of problem \(P\) corresponding to the green area in Figure 4.
We can rewrite this inequality as \(x_1 \geq \frac{6-x_2}{10}\), and apply interval arithmetic to bound the function
\(\frac{6-x_2}{10}\), between 0.2 and 0.5 (see example in FBBT section), to obtain the inequality \(x_1 \geq \frac{6-x_2}{10} \geq 0.2\).
Therefore, we can change the bounds of \(x_1\) in \(P\) from \([0,4]\) to \([0.2,4]\). In this case, the lower bound found using constraint propagation corresponds to the tightest bound possible for \(x_1\) (\(l^*_1\) in Figure 4). Note that if the original upper bound of \(x_1\) was \(0.1\) instead of \(4\) we could have concluded that the problem was infeasible.
Putting this into Practice
The idea is to apply constraint propagation to all the linear constraints in the problem. In general, using a linear equality constraint
\(\sum_{i=1}^{n}a_{i}x_{i}=b\)
we can bound all variables \(x_{i}) ((i =1, \dots,n)\) from below and above (depending on the sign of the coefficient \(a_i\)) by the values
\[\frac{1}{a_{i}}(b-\sum_{j=1\\ j\neq i}^{n}\min(a_j l_j,a_j u_j)),\]
and
\[\frac{1}{a_{i}}(b-\sum_{{j=1\\j\neq i}}^{n}\max(a_{j}l_j,a_{j}u_j)),\]
where \(l_j \leq x_j \leq u_j \forall j \neq i\). These values often provide bounds for \(x_i\) which are tighter than the original lower and upper bounds \(l_i\) and \(u_i\), or can provide us with a certificate of infeasibility for the problem.
Note that for linear constraints of lesser or greater sense you can derive the corresponding one-sided bounds.
One iteration of the constraint propagator consists of applying the technique once to every linear constraint.