Re: Branch & bound for not everywhere defiend constraints
Arnold Neumaier wrote:
> Nate Hayes schrieb:
>> 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.
>
> This is Alexandre Goldsztijn's example.
Ok. Sorry.
>> 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.
>
> Not only unneccesary effort. Much worse: there remains a spurious
> circle that cannot be eliminated at all. This may matter in
> applications!
No. The circle is not accepted as any part of the solution set. It just
represents some wasted effort.
> However, overall it is a performance win,
>
> In this example, the number of boxes is a factor of 1.6 larger
> compared to the number needed for the evaluation without NaI. This
> factor becomes worse when there is some overestimation in the range
> enclosures, and can become arbitrarily large by changing the example
> to one in which the undefined part has a more complex boundary.
>
> Where is the 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.
>
> With any reasonable implementation,this can never be more than a
> factor of 2. But with sufficiently sophisticated circuitry, the
> factor can be brought close to 1.
In normal evaluation modes, an array of values is processed
for ( int i=0; i < n; i++ ) z_i = a_i + b_i / c_i
However, in data-parallel mode
for ( int i=0; i < n; i++ ) tmp_i = b_i / c_i
for ( int i=0; i < n; i++ ) z_i = a_i + tmp_i
So in this case, n memory states must be allocated, preserved, and managed
by the user for n sets of flags. This assumes the hardware actually provides
one unique set of flags for each z_i in a vector register, which might not
be true (in which case you can't perform the computation reliably at all).
Even if the hardware supports unique flags, it doubles the bandwith to the
processor and pollutes the cache, as well as requring extra memory. The
performance loss can be significant, not to mention a sophisticated and
error-prone implementation required by the user. With NaI, the vector
processing can be performed in its usual, optimal configuration.
Nate Hayes