Re: Branch & bound for not everywhere defiend constraints
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.
Best regards,
Alexandre Goldsztejn
--
Dr. Alexandre Goldsztejn
CNRS - University of Nantes
Office : +33 2 51 12 58 37 Mobile : +33 6 78 04 94 87
Web: www.goldsztejn.com
Email: alexandre.goldsztejn@xxxxxxxxxxxxxx