Tagged intervals (Was Branch & bound for not everywhere defined constraints)
This thread reminds me of a discussion that MIGHT be slightly related: Tagged intervals.
Please set aside concerns of execution speed for a moment (yes, that's hard for me, too). Also, set aside my frequent calls for KISS.
One of the challenges is that an internal representation of an interval as two doubles (whether endpoints or mid-radius) does not have enough expressive power for everything some people want to know about an interval as it enters into various operations. Was there a discontinuity (or non-differentiability) encountered? Taken to an extreme, we might like to know the expression that can be evaluated to get its value, so we can optimize for tightness if we want. I might want to express that the interval is open at one end. Many other possibilities in various applications.
Over several years, I have had this discussion with several different people. Lee Winter most heavily influenced me. The sum of their arguments has convinced me that in many applications, [double, double] is not rich enough, not matter how many flavors of NaI one proposes. Many applications need tags. Not all.
In an object-oriented software design, we could define a class DecoratedInterval that is a [double, double] and whatever attribute tags we wanted. Objects of class DecoratedInterval would propagate their values and their tags however we programmed them to do so. The class DecoratedInterval could be built to have all the expressive power we needed for our specific application. ["Decorated" comes from the book Design Patterns. Recommended reading.]
OF COURSE a standard for class DecoratedInterval would violate KISS BIG TIME, and it would risk losing a speed contest with a glacier :-)
Isn't the P1788 standard for the interval that DecoratedInterval would decorate? That is, our class Interval is the SIMPLE interval. Sure, we want it to be as rich and expressive as we can design, but we should expect that in many applications, the expressive power will come from application-specific decorations, so the core class Interval can remain SIMPLE and FAST. Then applications that do not need decorations will enjoy good performance.
It violates KISS to burden the P1788 standard with the decorations each one of us sees as essential for OUR application. In some sense, P1788 is an intersection of requirements, not a union. I do not mean that literally, but I DO mean it SHOULD not do everything everyone wants. I think it is a better standard if it leaves everyone a bit disappointed THEIR favorite decoration was not included.
George
Dr. George F. Corliss
Electrical & Computer Engineering
Haggerty Engineering #296
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave.
Milwaukee WI 53201-1881
George.Corliss@xxxxxxxxxxxxx
414-288-6599; -288-4400 (GasDay); -288-5579 (Fax)
Www.eng.mu.edu/corlissg
On 9/5/09 6:49 AM, "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx> wrote:
> Date: Fri, 04 Sep 2009 22:41:44 -0500
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>, stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Branch & bound for not everywhere defined constraints
>
> Please see my inserted comments.
>
> Baker
>
> Dan Zuras Intervals wrote:
> >> Date: Thu, 3 Sep 2009 12:53:16 -0400
> >> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> >> Subject: Re: Branch & bound for not everywhere defiend constraints
> >> To: STDS-1788@xxxxxxxxxxxxxxxxx
> .
> .
> .
> >
> > As I said, no computers were harmed in this process
> > so even this order may have problems.
> >
> > What do you think now? Am I there yet?
> >
> > That's what I get for wetware compiling. :-)
> >
>
> From what I gather in this mostly 3-way exchange between
> Nate, Arnold, and Dan, there are various implementations of the
> branch and bound algorithm depending upon whether we have
> multiple NaI or not, and the main issue is one of efficiency.
Nate & I mostly. I haven't heard from Arnold yet.
Nate is teaching me about branch & bound & I ask
about different approaches. It is all very
entertaining. :-)
>
> First, I wish to thank Nate for posting his example of actual
> computation. Second, I'm a bit confused about
>
> (a) what is actually most efficient, and
>
> (b) what is being proposed for multiple NaIs (that is, how
> it is envisioned they might be implemented).
>
> Along these lines, might it be worthwhile for someone to
> volunteer to actually implement, somehow, the alternatives
> in a way that they CAN be experimentally compared?
Nate & I have been batting around a few examples
& he has been providing his paving plots to back
up his arguments.
Nate, I don't want to volunteer you for something
but are you set up to do this?
>
> One issue which would seem to impact practicality of the
> standard and simplicity of the specification is whether
> the NaI (or NaIs) is envisioned as a global flag(s) or whether we mandate
> it (them) as a part of the interval datum. Such things have
> been argued here, but it isn't clear to me what the implications
> of choosing one or the other of these alternatives is, other than
> that part of the datum seems simpler to describe and specify in
> a standard, at least at first glance. I'll need to rely on
> others to shed more light on these things.
>
> Baker
>
This is the issue Vincent & I kicked around a while
back.
I had in mind the interval analog of an old Forth
implementation of 754 which, having no global state,
chose to attach status bits (flags & modes at the
time) to each floating-point result.
Thus the status of any result was the inclusive OR
of the status of its operands together with any new
events that popped up during this operation.
Its simple. Its local. Its easy to understand.
The status that gets set is only the status that
contributed to THIS result & is not contaminated
by unrelated things being done in parallel. It
avoids the correctness proof problems that global
flags cause. It all but cures baldness. :-)
Still, Vincent & I could not work out the details.
I would propose some status flags like empty,
non-singleton, infinite width, half a dozen NaIs, &
some other things I could look up in my notes if you
like.
But Vincent was able to shoot down each detail & he
eventually convinced me I was going about it all
wrong.
Still, I could write up something given the context
of your question if you think it might contribute
to the discussion.
Be prepared for lots of criticism, though. :-)
Yours,
Dan