Re: Branch & bound for not everywhere defined constraints
> 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