Re: Branch & bound for not everywhere defiend constraints
Alexandre Goldsztejn wrote:
> Dear Mr. Hayes and colleagues,
>
>> 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.
>
> The problem occuring using NaI in this way can be quite harmful. Here
> is a typical example of what Arnold Neumaier has pointed out:
>
> 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).
>
> 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.
>
> On the other hand, not using NaI, the interval evaluation of sqrt( x^2
> + y^2 - 9 ) for the intervals xx=[-3,3] and yy=[-3,3] is equal to
> [0,3], which allows rejecting this box in one interval computation!
>
> 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." There
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" for
evaluations like sqrt([-1,3]). As the picture shows, this easily allows the
branch-and-bound algorithm to eliminate large areas of the center disk very
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
