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

Associated CP Options:

dr/dr1003