Chaining

 $\Large\begin{array}{c}\beta\\ \\ \gamma\\ \end{array}\qquad\begin{array}{c}\frac{-Pr}{Pr}\\ \\ \frac{I^{\gamma}\ C.\ C^{\uparrow}}{Pr\ B\big|C}\end{array}$  HON! 

$${\boldsymbol{B}}$$
We are now ready to formulate an optimization problem for computing the requested

least upper bound.

$$\mathrm{FUSION}$$

$$\mathbf{\mu}_{\mathrm{{G}}}$$
 min i2[1:k I B ; Bi

$$\beta$$

 min i2[1:k I

 B ; Bi

 min( min i2[1:k I  B ; Bi ; min i;j2[1:k ;i6 j I B ; Bi + I  B ; Bj )))

$$\vec{\mathbf{z}}$$
$$\begin{array}{c c c}{{G}}&{{}}&{{G}}&{{\mathcal{B}\ B\,,\ C}}\\ {{u}}&{{,\,u}}&{{}}&{{K B\ B\,,\ C}}\end{array}$$
The system of linear inequalities J B ; C is dened as the least set of linear inequalities
$$\begin{array}{c c c c}{{B}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{G}}&{{B\setminus B,C}}\end{array}$$

## Lemma 4.4

a) If G G B B ; C)) satises J B ; C , then for al l conditional constraints H G)[u ; u KB B ; C such that G H, there exists uH u ; u with H uH G .

b) Let uH u ; u for al l H G)[u ; u KB B ; C such that G H. There exists G

G B B ; C)) with J B ; C and H uH G for al l nodes H with parent G.

Proof. a) For all nodes H with parent G let uH be dened by uH H = xG b) Let B 1, and for all nodes H with parent G let H be dened by H uH G 2

Theorem 4.5 Let X be the maximum of subject to I E ; E"and J E ; E".

a) Pr EL E"
)) X Pr E for al l Pr Mo E ; E".

b) There exists Pr Mo E ; E"with Pr E and Pr EL E ")) X Pr E .

 min( B;

![0_image_0.png](0_image_0.png)

$$\begin{array}{c c c c}{{}}&{{}}&{{}}&{{G}}\\ {{}}&{{}}&{{H~G}}&{{u}}\end{array},u\begin{array}{c c c c}{{}}&{{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{}}&{{}}\end{array}$$

over G G B B ; C)) that contains B and u G H u G for all H G)[u ; u KB B ; C with G H (that is, G is the parent of H).

The intuition behind these denitions can now be described as follows.

Each G G B B ; C)) that satises J B ; C corresponds to the exact conditional constraint tree B B ; C ; KB0B ; C)), where KB0B ; C contains the pair H G)[ H=xG; xH=xG

and G H)[ ; v for each pair H G)[u ; u ; G H)[ ; v KB B ; C with G H
We will show that the least upper bound of Pr BL C)) Pr B), Pr BL C)) Pr B),

and Pr L C)) Pr B sub ject to Pr KB0B ; C and Pr B is given by I B ; C),
I

 B ; C), and I
 B ; C), respectively. It will then follow that the least upper bound of Pr BL C)) Pr B), Pr BL C)) Pr B), and Pr L C)) Pr B sub ject to Pr KB B ; C
and Pr B is given by the maximum of I B ; C), I
 B ; C), and I
 B ; C), respectively, sub ject to all G G B B ; C)) satisfying J B ; C).

That is, we implicitly performed the variable transformation described in the two examples. This transformation is indeed correct for conditional constraint trees:
