[gecode-users] Non-monotonic propagator.

[Guido Tack]

Zampelli Stephane wrote:
> Suppose one has a non-monotonic propagator P, because the propagator
> uses an approximation (of a NP-Hard problem) of the pruning.
> How can Gecode accomodate of this situation?
> Does this mean that recomputation cannot be used?

Recomputation will almost certainly fail (i.e., segfault or throw an  
exception) if non-monotonic propagators are present.

> Is the result correct if the recomputation is not used (full copying,
> c_d=1)?

Yes.

> What about executing the propag P after the fixpoint of all other
> monotonic constraints?

That looks like a solution in principle, but won't work in practice.   
The problem is that the space is not going to be stable (i.e. at a  
fixpoint) after running P.  Spaces in Gecode can only be copied at  
fixpoints.  You could iterate the normal fixpoint computation and the  
invocation of P until you reach a mutual fixpoint.  Still, this is not  
guaranteed to work with batch recomputation, where only one fixpoint  
is computed for each backtrack.

We have thought a bit about how to accomodate non-monotonic  
propagators, but it's really not easy.

Cheers,
	Guido