Re: Branch & bound for not everywhere defiend constraints
> Date: Thu, 3 Sep 2009 12:11:33 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> 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
The algorithm could be made more efficient by using
many NaIs. Or by using none as I suggested.
The question before us is: Which is to be preferred?
Dan