[gecode-users] BAB, constrain() and redundant cost constraints
petert at itu.dk
Sat Apr 14 19:32:06 CEST 2007
I have a quick question on the use of Branch and Bound.
>From the examples Warehouses and Golomb i can see that upon finding a
solution gecode will call constrain() on further spaces in order to
trim the search space so that it only includes better solutions.
This seems to be done by for example posting a linear constraint to
enforce a better a cost on the next solution. My question is simply
this: Isnt it true that these added constraints will accumulate
instead of replacing each other ( which is possible since each should
be tighter than the previous)?
Ie, you start by adding ax < 10, then find a solution with cost 9, and
add ax < 9, but leaving the propagator for ax < 10 alive. I realize
this will only add up to at most the number of variables propagators,
but i just want to make sure i am not missing something here :)
More information about the gecode-users