Next: Computational Complexity
Up: The Algorithm In Detail
Previous: The Algorithm In Detail
For all
we perform the same action. First we set
up the and for the LPproblem, since this
depends only on
and the already computed bounds for which
. The number of variables in our
LPproblem obviously is
. The number of
(inequality) constraints is equal to

(11) 
Once the LPproblem 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 LPproblem 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
20030818