

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

Figure 2: The area in which q ( s 1 s 2 ) must lie is shown. q (00) is implicitly given since the distribution is normalized.  a) The pyramid is the allowable space.  The darker planes show how this pyramid can be restricted by adding earlier computed bounds as constraints in the linear programming problem. b) This results in a smaller polyhedron. The black lines show the planes where the function Es, s, p (so = 1 | s, s2) q (s, s2) is constant for this particular problem.
In this way, information collected by bounds computed earlier, can propagate to S marry thereby finding tighter bounds for these marginals. This process can be repeated for all sets of marginal nodes we have selected until convergence is reached.

## 2.1 Linear Programming

In terms of standard linear programming, Equation 5 can be expressed as

$$\operatorname*{max}\left\{{\vec{c}}\cdot{\vec{x}}\;{\Big|}\;{\vec{x}}\geq0\,\land\,A{\vec{x}}\leq{\vec{b}}\,{\Big\}}\right\}$$
$$\left(\,{\boldsymbol{7}}\,\right)$$

where the variables are defined as

p ( Smar Soth = sep ) = p ( Smar | Ssep ) b = A = A Sinar C Sep A 3 mar E Sin - 6 ( Smar , Ssep ) -p- ( Sma

$$\begin{array}{l}{(8)}\\ {\qquad(9)}\end{array}$$  $$\begin{array}{l}{(10)}\end{array}$$ . 
where δ( s mar, s, ep ) = 1 iff the states of the nodes both node sets have in common are equal. Thus the columns of the matrix A correspond to s, constraints (of which we have 2 11 S nar 11 for each S nar ⊆ S rep ). The ordering of the rows of A