[eclipse-clp-users] Disjunctive/table constraints

From: Joachim Schimpf <jschimpf_at_coninfer.com>
Date: Mon, 08 Jul 2013 17:49:34 +0100
This is a question from a few weeks ago, which I don't want to
leave unanswered:

On 23/06/2013 13:04, Claudio Cesar de Sá wrote:
...
> 2. Really, the original idea is to formulate deterministics constraint like:
>
>   (  X_var #= [1, 1, 0, 0]
>      OR
>     X_var #= [0, 1, 1, 0]
>     OR
>     X_var #= [0, 0, 1, 1]
>    )
>
>   As I could not  find something to simulate this OR  elegantly,
> I used the member predicate, from a traditional logical programming.
>
> For a next time, how I can simulate a OR over an  option list?


There are several ways to do this.  The most elegant is probably
to use our magic library(propia), which can turn nondeterministic
code into a deterministic constraint by simple annotation:

:- lib(ic).
:- lib(propia).

dis1(Xs) :-
	(
	    Xs = [1, 1, 0, 0]
	;
	    Xs = [0, 1, 1, 0]
	;
	    Xs = [0, 0, 1, 1]
	) infers ac.


The 'ac' stands for 'arc consistency' and describes the resulting
constraint propagation behaviour.  For example:

?- dis1([X1, X2, X3, X4]).
X1 = X1{[0, 1]}
X2 = X2{[0, 1]}
X3 = X3{[0, 1]}
X4 = X4{[0, 1]}
There are 4 delayed goals.
Yes (0.00s cpu)

?- dis1([X1, X2, X3, X4]), X1 = 1.
X1 = 1
X2 = 1
X3 = 0
X4 = 0
Yes (0.00s cpu)

?- dis1([X1, X2, X3, X4]), X1 = 0.
X1 = 0
X2 = X2{[0, 1]}
X3 = 1
X4 = X4{[0, 1]}
There are 2 delayed goals.
Yes (0.00s cpu)


The way the library achieves this (in this case) is by rewriting
the code into element/3 constraints -- as you can see by inspecting
the delayed goals.

Of course, you can do the same reformulation by hand.  The idea is
to introduce an index variable I to represent the 3 alternatives,
resulting in:

dis2([X1,X2,X3,X4]) :-
	element(I, [1,0,0], X1),
	element(I, [1,1,0], X2),
	element(I, [0,1,1], X3),
	element(I, [0,0,1], X4).

This has the same behaviour as the code above.


A third possible formulation is using reified constraints:

dis3([X1,X2,X3,X4]) :-
	[X1,X2,X3,X4] :: 0..1,
	(
	    X1#=1 and X2#=1 and X3#=0 and X4#=0
	or
	    X1#=0 and X2#=1 and X3#=1 and X4#=0
	or
	    X1#=0 and X2#=0 and X3#=1 and X4#=1
	).

but note that this has weaker constraint propagation behaviour,
and does not achieve arc-consistency:

?- dis3([X1, X2, X3, X4]), X1 = 0.
X1 = 0
X2 = X2{[0, 1]}
X3 = X3{[0, 1]}
X4 = X4{[0, 1]}
There are 17 delayed goals.
Yes (0.00s cpu)


Cheers,
Joachim
Received on Mon Jul 08 2013 - 16:49:46 CEST

This archive was generated by hypermail 2.2.0 : Tue Jul 09 2013 - 06:14:09 CEST