Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
> If I read his little lines correctly, the subdivision
> of boxes proceeds in a fairly efficient manner until it
> reaches an epsilon which appears to be at a box which
> is 1/64 on a side.
>
> EXCEPT in the blue (NaI or indeterminate) region.
>
> Where it forms the boundary between the gray region
> (f(X) > 0) & the green region (-oo < f(X) <=0) it is an
> indeterminate with the expected 'set of measure zero'
> property of a boundary & subdividing to some epsilon
> limit is the efficient & expected behavior.
>
> BUT your use of NaIs as a proxy for both indeterminate
> & empty means that the entire undefined & therefore empty
> regions within the green teardrops is treated by your
> algorithm as indeterminate. Therefore, you continue to
> subdivide this (now non-trivially positive measure)
> region over & over again until you reach your epsilon
> limit.
>
> A VERY inefficient use of your resources both in space
> & time.
Hi Dan,
Yes this is a good a correct observation. However, that example uses one
unique NaI. I mention at the end of that post the several NaIs idea could
improve this situation. It can be accomplished, e.g., by encoding
"TotallyUndefined" or "PossiblyUndefined" within the NaI as in the Paving C
example. In Paving B, this would eliminate the large areas of wasted effort,
i.e., the blue teardrop-like areas in the right side of the picture.
Nate Hayes