Re: [eclipse-clp-users] Reified constraint without propia

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Wed, 28 Apr 2010 10:31:57 +1000
Philipp Marcus wrote:
> Hi,
> 
> I wanted to write a custom reified constraint  and already created the
> mycon(...,1) and the mycon(...,0) version. Then I wanted to combine them
> with propia to say mycon_constr(...,B) :-
>     mycon(...,B) infers most.
> 
> But now I have the following problem:
> calling mycon_constr(...,1) gives me less propagation than calling
> mycon(...,1). But in my opinion it should reduce the variable bounds to
> the same intervals (I'm using ic).

Using infers/2 only makes sense when you apply it to a nondeterministic
(i.e. more than one solution) predicate.  For example the following
gives you 3 solutions:

?- member(X, [1, 2, 3]).
X = 1
Yes (0.00s cpu, solution 1, maybe more)
X = 2
Yes (0.00s cpu, solution 2, maybe more)
X = 3
Yes (0.00s cpu, solution 3)

and by wrapping this in infers/2 you get a single solution which is
the "convex hull" of the alternative solutions:

?- member(X, [1, 2, 3]) infers ic.
X = X{1 .. 3}
Yes (0.00s cpu)

Only in the latter case do we talk about "propagation".
If you have the impression that your unannotated predicate gives
your more "propagation", then you may have overlooked that you get
alternative solutions that need to be taken into account as well.


> 
> Now I thought of doing the reified stuff by my self, instead of using
> propia in order to circumvent the problem. So I wanted to ask if there
> is general pattern that fulfills the requirements for the three situations:
> 
>     * Reified variable is unbound (check if constraint is entailed)

You also want to check if the constraint is disentailed (i.e. whether
you can bind the Boolean to 0).

>     * Reified variable is bound to 0
>     * Reified variable is bound to 1
> 
> Especially I'd like to know how to realize the first case best. Would
> you use suspend to do that? And how would you do that?

The implementation of a reified constraint is not really any different
from any other constraint - you just have an extra argument.
For example, if your original constraint has the following truth table:

and(0,0,0).
and(0,1,0).
and(1,0,0).
and(1,1,1).

then the reified version has this one

and_reif(0,0,0,1).   % the entailed cases
and_reif(0,1,0,1).
and_reif(1,0,0,1).
and_reif(1,1,1,1).
and_reif(0,0,1,0).   % the disentailed cases
and_reif(0,1,1,0).
and_reif(1,0,1,0).
and_reif(1,1,0,0).

and you can make either into a constraint by using infers/2, e.g.

?- and_reif(0, Y, 1, B) infers ic.
Y = Y{[0, 1]}
B = 0
Yes (0.00s cpu)


For an example of direct implementation without propia, look at the library
source file sd.ecl, which implements a reified predicate (&\=)/3.


-- Joachim
Received on Wed Apr 28 2010 - 00:30:15 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET