Re: How do I bisect unbounded intervals?

["Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>]

Baker Kearfott wrote:

> P-1788:
>
> Although I find this topic interesting and am glad it is
> being discussed, I now wish to express a personal opinion
> about its relevance to P-1788.  Namely, in my own
> view, I think specifying a "bisection point" in a
> branch and bound algorithm is too application specific to
> be a part of our standard.  I think specifying "midpoint"
> is well within the scope, in which case we may wish to specify
> what is returned for unbounded intervals (just so it will
> be known and standard across platforms;  however, IMO specifying
> "random" in such cases won't help in portability and reproducibility).
> However, specifying "bisection point" different from midpoint, and
> designed to be good for branch and bound algorithms, seems a bit
> of a stretch of the scope.


Ok.

Perhaps in that case we can at least consider a definition for our
"midpoint" operation that does not lead unsuspecting users into some of
these well-known traps and pitfalls? For example, if the midpoint of any
unbounded interval would be some finite Level 2 datum or NaN, then this may
accomplish that.

In my experience simple midpoint bisection works amazingly well for a large
class of B&B problems. I suspect many users will be tempted to just use the
"midpoint" operation to design thier own algorithms. So defining the
operation in such a way that it does not easily allow results that can lead
to infinite recursion, this may at least force users to think about how to
design thier own bisection algorithms more carefully.

Nate

P.S.

May I even be so bold as to suggest the "midpoint" of any interval [u,v]
could be NaN if u and v are two adjacent Level 2 datums, regardless if u and
v are both finite or not? The rationale: this also avoids infinite recursion
in naive B&B algorithms if midpoint of [u,v] is otherwise defined to be u or
v.