[m-rev.] removing deep_profiler/branch_and_bound.m

[Paul Bone]

On Sat, Dec 20, 2014 at 11:39:46PM +1100, Zoltan Somogyi wrote:
> This module is not needed anymore. Any objections to removing it?
> All opinions welcome, but I definitely want Paul's.

It's okay to remove this.  I'll try not to be precious :-)


> I thought about just moving it to samples or extras, but really, the best
> way to implement branch and bound is to exploring different branches
> in different conjuncts (the way the deep profiler now does it), not in
> different disjuncts (the way branch_and_bound does it), since the latter
> requires lots of impurity to transmit information across branches.
> I wouldn't want to give people the impression that this impurity is
> the best way to code this algorithm.

I think that both have their merits.  I don't think this one has too much
impurity but that's a subjective judgement.  branch_and_bound.m is _a_ valid
solution to the problem.

I'm aware that my original branch and bound code had a bug that went
undected because of the style that I chose.  The result was that it ran in
O(N^3) time rather than O(N^2) time.  Each decision in the tree had two
options, so the tree had a quadratic size.  My code was nondet and I didn't
get a determinism warning when a goal had more solutions than I expected.
So it's not just the impurity that was a problem with this approach.

Anyway, what I'm trying to say is that I don't think that one style is
_always_ best but I do agree that this probably shouldn't go into samples or
extras.  Due to the impurity, it's not a good example of how you'd normally
solve this problem _in Mercury_.

Cheers.

-- 
Paul Bone