Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
>>> There is another thing to consider & another reason to
>>> keep things like decorations at the level of an
>>> abstraction.
>>>
>>> So long as we specify that a decorated interval consist
>>> of an 'undecorated' interval together with an associated
>>> decoration, we have said nothing about how that decoration
>>> appears or how it is associated with the interval.
>>
>> No. This absolutely rules out the entire NaI concept.
>
> Other than in name, I don't see how.
Ok. I'm sorry. Here is what I mean:
To me "decorated interval" has a very specific meaning from Design Patterns.
In this case, a decorated interval is an abstract ideal representing some
structure or aggregate comprised of an undecorated interval and its flags
bits. The implementations may vary, but a decorated interval always has two
portions: the undecorated interval portion and the decoration portion.
NaI just represents the decoration and does not have an undecorated portion
(that part is lost when NaI is instantiated).
>
>>
>> . . .
>>
>>>
>>> An adequately clever implementation might choose to store
>>> the interval part in one place & the decoration somewhere
>>> else & count on a similarly smart compiler to maintain
>>> the association. So, for example, arrays of intervals
>>> parts could be packed up efficiently on power-of-two
>>> boundaries with arrays of their decorations stored
>>> elsewhere (perhaps ALSO on smaller power-of-two
>>> boundaries).
>>>
>>> Such an approach has its merits (it eliminates all your
>>> valid complaints)
>>
>> Nothing is further from the truth!
>
> Really?
>
>>
>> I think you miss the most important facts about NaI:
>
> Do I?
>
>>
>> For the branch-and-bound algorithms, everything you describe is
>> entirely unneccesary. All that a user needs to get up and running
>> with fast branch-and-bound using NaI can be written in a few pages
>> of C++ code; it only uses power-of-two datatypes; and it does not
>> chop the interval datatype into two separate pieces of memory that
>> must be managed separately by a compiler and specialized hardware.
>
> It all seems entirely equivalent to me. The issue of
> power-or-two in size is not so important as you make it
> out to be, IMHO. The rest is a question of the choices
> an implementation makes to beat its competition.
I believe the question is deeper than implementation: is there an example of
interval algorithms at the mathematical level that actually require both
portions of a decorated interval?
Alexandre's fixed-point example, as originally presented, required both
portions. But when reformulated into a branch-and-bound problem, this
mutual dependency no longer exists (so NaI is adequate).
If decorated intervals are not required at the mathematical level, I wonder
why are they required at the implementation level? That is what I do not
understand.
Nate Hayes