[gecode-users] Non-monotonic propagator.

[Christian Schulte]

Hi,

actually we have been thinking some more, driven also by the fact that we
have a non-monotonic propagator ourselves. 

So, Gecode 3.0 will support non-monotonic propagators. What we have to do,
still, is to spell out the invariants and guarantees one still gets when
using non-monotonic propagators (the key here will be that the existence of
solutions does not change). It looks reasonably straightforward for all but
Gist (so, Gist will warn now and then that it might recompute something
slightly different).

Cheers
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Guido Tack
Sent: Tuesday, July 01, 2008 5:33 PM
To: Zampelli Stephane
Cc: users at gecode.org
Subject: Re: [gecode-users] Non-monotonic propagator.

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


_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users