Valeurs pertinentes pour $\Delta (b)$

Comme nous sommes dans un problème de minimisation, il est possible de définir des restrictions sur les valeurs que peuvent prendre chaque variable. Par exemple, un intervalle $[3; 7]$ peut se réduire à un ensemble de valeurs $\lbrace 3, 6, 7 \rbrace$. Nous allons commencer par les extremums pouvant être pris par $\Delta (b)$. Tout d'abord, nous définissons :

$$x_{min}(C(b_{1}, b_{2}))\ =\ x_{l}\ et\ x_{max}(C(b_{1}, b_{2}))\ =\ x_{1}$$

$$y_{min}(C(b_{1}, b_{2}))\ =\ y_{1}\ et\ y_{max}(C(b_{1}, b_{2}))\ =\ y_{l}$$

En utilisant ces notations, on désigne de même les extremums :

$$\Delta_{min}(b) = \max\{\max_{b^{\prime} \in \mathcal{B}} x_{... ... \max_{b^{\prime} \in \mathcal{B}} y_{min}(C(b^{\prime}, b))\}$$

$$\Delta_{max}(b) = \max\{\max_{b^{\prime} \in \mathcal{B}} x_{... ... \max_{b^{\prime} \in \mathcal{B}} y_{max}(C(b^{\prime}, b))\}$$

$\Delta_{min}$ correspond au plus petites valeurs acceptées par toutes les clauses et $\Delta_{max}$ est la plus grande valeur trouvée dans toutes les clauses. Une fois cela fait, on définit pour chaque buffer $b \in \mathcal{B}$, les valeurs potentielles $\Delta^{i}(b),\ i=0, \ldots, k(b)$ de la façon suivante :

1. $\Delta^{0}(b) \leftarrow \Delta_{min}(b)$;
2. $i \leftarrow 1$;
3. soit $x$ la plus petite valeur telle que $x>\Delta^{i-1}(b)$ et il existe une expression contenant l'inégalité $\Delta(b) \geq x$;
4. si un tel $x$ existe : $\Delta^{i}(b) \leftarrow x$;
5. $i \leftarrow i + 1$;
6. retourner en 3;
7. sinon : $k(b) \leftarrow i$.