The Iterative Part

For all $S_\mathrm{\scriptscriptstyle sep}\in\Omega$ we perform the same action. First we set up the $A$ and $\vec b$ for the LP-problem, since this depends only on $S_\mathrm{\scriptscriptstyle sep}$ and the already computed bounds for which $S_\mathrm{\scriptscriptstyle mar}'\subseteq S_\mathrm{\scriptscriptstyle sep}$. The number of variables in our LP-problem obviously is $\left\Vert S_\mathrm{\scriptscriptstyle sep}\right\Vert$. The number of (inequality) constraints is equal to

$$\sum_{S_\mathrm{\scriptscriptstyle mar}'\subseteq S_\mathrm{... ...sep}}2\left\Vert S_\mathrm{\scriptscriptstyle mar}'\right\Vert$$ (11)

Once the LP-problem is set up this far, we try to improve all bounds that are defined over an $S_\mathrm{\scriptscriptstyle mar}$ for which $S_\mathrm{\scriptscriptstyle sep}$ is its separator. The separator in figures b and d, for instance, is identical, but the $S_\mathrm{\scriptscriptstyle mar}$'s differ. For each bound we iterate over its state space and set the $\vec c$ as in Equation  to its appropriate value. Then we compute the new upper and lower bounds for that $\vec s_\mathrm{\scriptscriptstyle mar}$ by solving the LP-problem twice: maximize and minimize. If the new found value improves the bound, we store it, otherwise we abandon it.

The iterative procedure is repeated until convergence is reached. In our simulations we define a bound as being converged as soon as the relative improvement after one iteration is less than one percent. If this holds for all bounds, the algorithms stops.