clpBNR: difference constraint on reals

Help!
17

This thread got somewhat side tracked into a discussion of mechanics, so for the record:

For finite domains (integers) clpBNR provides equivalent semantics to clpfd. As a proof of concept, here’s a predicate which maps a clpfd domain expression (X in Dom) to clpBNR constraints:

fd_BNR(X in N) :- integer(N), !, X=N.
fd_BNR(X in L..H) :- !, X::integer(L,H).
fd_BNR(X in Dom) :-
    fd_map_domains(Dom,X,1.0Inf,-1.0Inf,Min,Max,Cs),
    X::integer(Min,Max),
    {Cs}.

fd_map_domains(D1\/D2,X,MinIn,MaxIn,Min,Max,(Cs or C)) :- !,
    fd_map_domains(D1,X,MinIn,MaxIn,Min1,Max1,Cs),
    fd_map_domains(D2,X,Min1,Max1,Min,Max,C).
fd_map_domains(D1,X,MinIn,MaxIn,Min,Max,C) :-
    fd_map_domain(D1,X,Min1,Max1,C),
    Min is min(MinIn,Min1),
   Max is max(MaxIn,Max1).

fd_map_domain(L..H,X,L,H,(Xl=<X,X=<Xh)) :- !,
    Xl is min(L,H), Xh is max(L,H).
fd_map_domain(N, X,N,N, X==N).

A clpfd query:

?- X in 8..10\/1..3, label([X]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 8 ;
X = 9 ;
X = 10.

and using fd_BNR:

?- fd_BNR(X in 8..10\/1..3), enumerate(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 8 ;
X = 9 ;
X = 10.

The clpfd query:
?- X in 8..10\/1..3, Y in 8..10\/1..3, X#\=Y, label([X,Y]).
is equivalent to:
?- fd_BNR(X in 8..10\/1..3), fd_BNR(Y in 8..10\/1..3), {X<>Y}, enumerate([X,Y]).

Now the original post questioned whether this be extended to the continuous domain of reals? And it can to a limited degree. The constraints themselves are fine and will be imposed on any solution. However, in the limited context of this last example there are two problems.

First, “’<>’” has no sound meaning in the real domain. (For this reason clpBNR restricts its use to integers.)

Second, you can’t “enumerate” a set of reals which has an infinite number of members. So to find solutions, you need to rely on additional constraints and/or search mechanisms relevant to the specific problem. For the simple case where a real can only have a relatively small number of discrete values, the best approach would seem to be a custom labelling predicate which generates them. When X and Y are point values, the constraint {~(X==Y)} can be used for inequality.

Note that neither clpfd or clpBNR has any direct support for the notion of subdomains, e.g., inequality of subdomains can’t be expressed. But internally clpfd can represent domains with “holes” so it should be more efficient for those fd problems with sparse domains.

2 Likes