# Constraint Propagation (CP)

What is Constraint Propagation (CP)?
Putting this into Practice
Associated CP options

## 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.