Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Branch & bound for not everywhere defiend constraints

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.



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!


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.


Arnold Neumaier