[gecode-users] nested cost functions

[Mikael Zayenz Lagerkvist]

On 09/20/2011 06:36 AM, revo revo wrote:
> Thanks. One thing I'm confused by is that in talking to fellow 
> colleagues, they say that branch and bound isn't related to constraint 
> programming. But from the manual and Schulte's "Programming Constraint 
> Inference Engines", it seems like a best solution search using BAB is 
> one form of constraint programming.
>
> Maybe if someone could direct me towards a tutorial that sharpens the 
> distinction between best solution search CP and optimization and how 
> BAB fits into gecode's CP framework (I thought I understood it as a 
> search technique, but now I'm being told it's unrelated to CP), I 
> would be enlightened.

The short answer is that there are more than one area that uses the term 
branch and bound. The CP usage of the term has slightly different 
terminology than the usage in mathematical programming*, but the main 
principles are the same.

There are lots of resources for learning how BAB works in constraint 
programming (lecture notes from CP courses at universities is a good 
start), and that does not really have to do with Gecode.

Cheers,
Mikael

* Essentially, the bounding of the math programming kind is actually 
constraint propagation, and the pruning in the math programming kind is 
the bounding in the CP terminology. One may argue the merits of the 
different sets terms (and of having different terms), but for CP the 
terms used make much more sense than the other set of terms would.


-- 
Mikael Zayenz Lagerkvist, http://www.it.kth.se/~zayenz