[gecode-users] BAB, constrain() and redundant cost constraints

[Guido Tack]

Hi!

Peter Tiedemann wrote:
> 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)?

In principle, this could happen, because you can post arbitrary  
propagators in the "constrain" function.

> 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 :)

You usually work around this problem by adding another variable (say  
"y") to your model, adding the constraint "ax < y" to your model, and  
then just adding constraints "y < 10", "y<9" and so on during branch  
and bound. These constraints are not represented as propagators, but  
just immediately shrink the variable's domain.

I think this model fits for most objective functions, but I would be  
very interested in an application where you can't avoid posting more  
and more real propagators during branch and bound.

Cheers,
	Guido