NaI's as decorated empty sets
Nate Hayes wrote
[in: Interval hardware and existing practice]:
In my view, the problem with decorated intervals is they don't appear to
provide any benefit or function that can't be achieved more simply and
efficiently with a few standardized NaIs, which would retrofit very nicely
into existing hardware.
I think those in favour of decorated intervals need to show why they are
absolutely necessary; even if this can be done, it should also be explained
why we CAN'T also have NaIs for the branch-and-bound algorithms.
The Paving C picture for Alexandre Goldsztjn's example
sqrt(x^2 +y^2-9) > 4
proves that the spurious inner circle is _never_ eliminated when using
NaI's, since any box with rational endpoints containing an irrational
point on this circle will evaluate to NaI.
Thus the decorated mode in place of NaI is absolutely necessary
for any branch and bound algorithm that leaves he user the choice
of how to write a given constraint. I don't want to be deprived of
this choice.
The NaI with payload is essentially equivalent to propagating only
the decoration while throwing away the interval. This saves space
but wastes information. In some cases, it may lead to a saving.
But it leads to a loss in all cases where both the interval and the
decoration contain useful information (e.g. in any interval Newton
method that wants to verify existence and uniqueness).
Thus the user should have a choice what to use.
This leads to an interesting possibility:
Perhaps we should treat NaI's as decorated empty sets!
This would make their processing fast, people who don't need them
can throw away all decorations and only need to propagate the
bare intervals, while those who can/need employ decorations
and/or NaI's can do so, too.
Arnold Neumaier