Re: Branch & bound for not everywhere defiend constraints
> Date: Thu, 3 Sep 2009 10:22:56 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
>
> Alexandre Goldsztejn wrote:
> > Dear Mr. Hayes and colleagues,
> >=20
> >> Sometimes in a set-covering problem, this can occur. It could be
> >> overcome by the several NaIs idea. For example, if a function is
> >> possibly undefined but also strictly positive, this information can
> >> be encoded in the NaI.
> >=20
> > The problem occuring using NaI in this way can be quite harmful. Here
> > is a typical example of what Arnold Neumaier has pointed out:
> >=20
> > Consider the constraint sqrt( x^2 + y^2 - 9) > 4. Its solution set is
> > the complement of the radius 5 disk centered on 0 (the constraint is
> > actually equivalent to x^2 + y^2 > 25).
> >=20
> > Using NaI, the interval evaluation of any box that intersects the open
> > radius 3 disk centered on zero will return NaI. Thus, a bisection
> > algorithm based on this interval evaluation will output a covering of
> > this disk made of tiny boxes, leading to a huge, spurious undecided
> > area, determined in an extremely inefficient way.
> >=20
> > On the other hand, not using NaI, the interval evaluation of sqrt( x^2
> > + y^2 - 9 ) for the intervals xx=3D[-3,3] and yy=3D[-3,3] is equal to
> > [0,3], which allows rejecting this box in one interval computation!
> >=20
> > In this example, there is no information to be attached to the NaI
> > that would help, excepted attaching the actual result of the interval
> > evaluation without NaI to this NaI, which seems to make no sense.
>
> With all due respect, I don't think Arnold and Alexandre fully understand=
>
> the idea of using the payload in the NaI.
>
> Attached is a paving of Arnolds example. According to Arnold, the center
> disk should be filled entirely with blue boxes representing "a huge,
> spurious undecided area, determined in an extremely inefficient way." The=
> re
> also should be "no information to be attached to the NaI that would help.=
> "
>
> However, it is just as easy to encode "TotallyUndefined" for evaluations
> like sqrt([-3,-1]) into the NaI as it is to encode "PossiblyUndefined" fo=
> r
> evaluations like sqrt([-1,3]). As the picture shows, this easily allows t=
> he
> branch-and-bound algorithm to eliminate large areas of the center disk ve=
> ry
> efficiently.
>
> There remains a circle at radius 3 where some unnecessary effort still
> remains. However, overall it is a performance win, as the overhead of
> sending along an extra byte for every calculation instead has potentially=
>
> much more dramatic implementation and performance overheads, particularly=
> in
> a data-parallel computing environment as mentioned before.
>
> Nate Hayes
>
Wish all due respect to you Nate I think your algorithm
could be made more efficient by eliminating the use of
NaIs in favor of <empty>.
First, let me ask everyone to look carefully at Nate's
'Paving B.png'.
If I read his little lines correctly, the subdivision
of boxes proceeds in a fairly efficient manner until it
reaches an epsilon which appears to be at a box which
is 1/64 on a side.
EXCEPT in the blue (NaI or indeterminate) region.
Where it forms the boundary between the gray region
(f(X) > 0) & the green region (-oo < f(X) <=0) it is an
indeterminate with the expected 'set of measure zero'
property of a boundary & subdividing to some epsilon
limit is the efficient & expected behavior.
BUT your use of NaIs as a proxy for both indeterminate
& empty means that the entire undefined & therefore empty
regions within the green teardrops is treated by your
algorithm as indeterminate. Therefore, you continue to
subdivide this (now non-trivially positive measure)
region over & over again until you reach your epsilon
limit.
A VERY inefficient use of your resources both in space
& time.
Let me suggest that a more efficient algorithm might be
had by eliminating this overloaded use of NaIs in favor
of the following:
If f(X) > 0 color me gray
else if 0 \in f(X) color me blue
else if width(f(X)) == +oo color me red
else if f(X) \subset [-oo,0] color me green
else if empty(f(X)) color me yellow
If ((red or blue) and |X| > epsilon) bisect X & recurse.
The (formerly) undefined teardrops within the green
regions are now colored yellow to indicate that no answer
is returned in these regions which is the correct
interpretation.
The yellow regions are bounded by a thin red boundary
also of 'measure zero'.
This is surrounded by the green region as before, which
is in turn bounded by a tiny blue boundary, followed by
the gray region.
And the algorithm is made more efficient in that the
(formerly) great expanse of overloaded blue NaIs is
thinned into two distinguishable boundaries & the non-
trivial undefined region which takes much less work to
find.
You might even be able to greatly reduce your epsilon
from 1/64 to something much more informative to the eye.
Let me make one other minor criticism in your original
problem statement which I include verbatim below.
You seem to count on the fact that "g(X') always returns
the optimal range enclosure in exact arithmetic."
Color me dubious that this is even possible in its full
generality or computationally efficient when possible.
But an efficient algorithm of this sort need not depend
on this behavior so long as the interval returned contains
the correct answer.
In a less-than-optimal calculation the red & blue boundary
boxes (which are the only ones that matter) may be
subdivided as normal but then may have to be subdivided
again in cases where new uncertainty is introduced by the
nature of the computation itself. The result will still
be of the 'measure zero' character. It will just be a
slightly larger 'zero' than before. :-)
Caveat: All this is from my visual inspection of Nate's
plots & his problem statement. No computers have been
harmed in this activity & I may be partially or
completely wrong in my conclusions.
I leave it to those more experienced than I to judge.
Yours,
Dan
------------------------
From Nate (1 Sep 2009):
Suppose the user gives us the function
g(x) := cos(x0)+sin(x1/exp(x0))+sqr(x0/x1)
and the function
f(x) := ln(g(x)).
Then a user asks us to perform a branch-and-bound method,
to within some tolerance, over the domain X = ( [-4,0],
[1,5] ) in order to find a subset
S := { x in X | f(x) <= 0, x is real, f(x) is real }.
So there should be no vacuous truth: if f(x) is undefined
(not real) at some x, then all those x should not be members
of S.
We define the branch-and-bound method as
if isEmpty(f(X')) then delete X' // yellow
else if f(X') > 0 then delete X' // gray
else if f(X') <= 0 then accept X' // green
else if eps(X') then mark X' indeterminate // blue
else bisect X'
where X' is any sub-box of X and eps(X') is a function to
determine if the sub-box meets tolerance criteria or not.
Assume for the moment that g(X') always returns the optimal
range enclosure in exact arithmetic. If g(X') = [-1,0.3]
for some X', then ln([-1,0.3]) is a domain overflow, so
(according to some current proposals) the interval argument
[-1,0.3] is intersected with the natural domain (0,Inf) of
the logarithm function
ln([-1,0.3]&(0,Inf)) = ln((0,0.3]) = (-Inf,ln(0.3)].