# Constraint Propagation (CP)

## What is Constraint Propagation (CP)?

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.

**Figure 4.**

## 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,$$
you 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\) for all \(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.