clpfd: Correlation between domains

[Michael Igler-2]

Hello,

take the following two clpfd - constraints:

1) A #>= 2, A #=< 3, B #>= 1, B #=< 3, C #>= 1, C #=< 2.

2) A #>= 2, A #=< 4, B #>= A, B #=< 3, C #= A + 1, C #= B + 1.

In 2) you have corelations between the domains, i.e. B #>= A

In 1) there are no correlations between each other. Every domain has a
number as inf and sup.

Now can I find out in a statement when a domain has correlations to  
other
domains and when not?

I.e. in 1) correlated(A) -> false

in 2) correlated(A) -> true because of B references to A


Mit freundlichen Grüßen / Best Regards

Mike

[Ulrich Neumerkel]

>Hello,
>
>take the following two clpfd - constraints:
>
>1) A #>= 2, A #=< 3, B #>= 1, B #=< 3, C #>= 1, C #=< 2.
>
>2) A #>= 2, A #=< 4, B #>= A, B #=< 3, C #= A + 1, C #= B + 1.
>
>In 2) you have corelations between the domains, i.e. B #>= A
>
>In 1) there are no correlations between each other. Every domain has a
>number as inf and sup.
>
>Now can I find out in a statement when a domain has correlations to other
>domains and when not?
>
>I.e. in 1) correlated(A) -> false
>
>in 2) correlated(A) -> true because of B references to A

You mean probably that X and Y are correlated in

?- X #= K*Y.

Except for K = 0.  Sometimes clpfd is clever enough to realize this.
Sometimes not.

?- X #= (A-B)*Y, A #>= B, B #>= A.
_G2745*Y#=X,
_G2745+B#=A,
B#>=A,
A#>=B.

?- X #= (A-B)*Y, A #>= B, B #>= A, A = B.
X = 0,
A = B,
B in inf..sup,
Y in inf..sup.

The general problem behind is undecidable, so you have to go for some
kind of approximation.  The simplest one would be start investigating
the neighbor variables that are attached to the same constraints.
copy_term/3 should suffice.  Finding a better form of approximation
seems to be the most difficult task here.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Michael Igler-2]

Thanx for you reply. My idea was that when you take:

?- B #>= A.

then the right side must evalute to a number (number/1). In this case  
it is false.
That should be sufficient for the moment.

To be honest, I did not get your idea of copy_term/3. Can you please  
give a small example?


Mit freundlichen Grüßen / Best Regards

Michael Igler
Dipl. Inform. (Univ.)

Universität Bayreuth
Fakultät für Mathematik, Physik und Informatik
Lehrstuhl für Angewandte Informatik IV

AI 0.25
D-95440 Bayreuth

Fon : +49 921 - 55 7625
Fax : +49 921 - 55 7622
Email : michael.igler@...
Internet : http://www.ai4.uni-bayreuth.de



Am 24.06.2009 um 14:57 schrieb Ulrich Neumerkel:

>> Hello,
>>
>> take the following two clpfd - constraints:
>>
>> 1) A #>= 2, A #=< 3, B #>= 1, B #=< 3, C #>= 1, C #=< 2.
>>
>> 2) A #>= 2, A #=< 4, B #>= A, B #=< 3, C #= A + 1, C #= B + 1.
>>
>> In 2) you have corelations between the domains, i.e. B #>= A
>>
>> In 1) there are no correlations between each other. Every domain  
>> has a
>> number as inf and sup.
>>
>> Now can I find out in a statement when a domain has correlations to  
>> other
>> domains and when not?
>>
>> I.e. in 1) correlated(A) -> false
>>
>> in 2) correlated(A) -> true because of B references to A
>
> You mean probably that X and Y are correlated in
>
> ?- X #= K*Y.
>
> Except for K = 0.  Sometimes clpfd is clever enough to realize this.
> Sometimes not.
>
> ?- X #= (A-B)*Y, A #>= B, B #>= A.
> _G2745*Y#=X,
> _G2745+B#=A,
> B#>=A,
> A#>=B.
>
> ?- X #= (A-B)*Y, A #>= B, B #>= A, A = B.
> X = 0,
> A = B,
> B in inf..sup,
> Y in inf..sup.
>
> The general problem behind is undecidable, so you have to go for some
> kind of approximation.  The simplest one would be start investigating
> the neighbor variables that are attached to the same constraints.
> copy_term/3 should suffice.  Finding a better form of approximation
> seems to be the most difficult task here.