Next: Computational Complexity Up: The Algorithm In Detail Previous: The Algorithm In Detail

## The Iterative Part

For all we perform the same action. First we set up the and for the LP-problem, since this depends only on and the already computed bounds for which . The number of variables in our LP-problem obviously is . The number of (inequality) constraints is equal to

 (11)

Once the LP-problem is set up this far, we try to improve all bounds that are defined over an for which is its separator. The separator in figures b and d, for instance, is identical, but the 's differ. For each bound we iterate over its state space and set the as in Equation  to its appropriate value. Then we compute the new upper and lower bounds for that 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.

Next: Computational Complexity Up: The Algorithm In Detail Previous: The Algorithm In Detail
Martijn Leisink 2003-08-18