Re: Branch & bound for not everywhere defiend constraints
> 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
>
> Dan Zuras Intervals wrote:
> > The algorithm could be made more efficient by using
> > many NaIs. Or by using none as I suggested.
>
> I don't entirely follow what you've suggested. For example, any assertion
> about the empty set is always vacuously true. So if f(X) is empty, then every
> if-then clause in
>
> If f(X) > 0 color me gray
> else if 0 \in f(X) color me blue
> else if width(f(X)) == +oo color me red
> else if f(X) \subset [-oo,0] color me green
> else if empty(f(X)) color me yellow
>
> is true. For example, f(X) > 0 is true if f(X) is empty. So I don't see how any
> yellow boxes will show up in your paving.
>
> Nate Hayes
Ah, you spotted that. :-) :-) :-)
Yes, I noticed it just after I posted it.
I believe (one of) the correct sequence(s) is:
if empty(f(X)) color me yellow
else if f(X) > 0 color me gray
else if 0 \in f(X) color me blue
else if width(f(X)) == +oo color me red
else if f(X) \subset [-oo,0] color me green
And still recurse on red & blue.
I think the logical constraints are yellow before
everyone (as you point out), both red & blue (in
either order) before green, & which leaves gray to
go anywhere after yellow.
If the domain of your search is expanded to include
a neighborhood of {x0 = 0, x1 = 0} then there is a
slight behavioral difference near the beginning of
the search if gray follows red but I don't think it
invalidates the results.
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. :-)
Enjoy,
Dan