How to use member predicate to specify constraints in prolog

Question

I'm trying to write a Prolog program which does the following: I have some relations defined in the Relations list. (For example: [f1,s1] means f1 needs s1) Depending on what features(f1,f2,f3) are selected in the TargetFeat list, I would like to create Result list using constraint programming. Here is a sample code:

Relations =[[f1, s1], [f2, s2], [f3, s3], [f3, s4]],
TargetFeat = [f3, f1],
Result = [],
member(f3,TargetFeat) #= member(s3,Result), %One of the constraints
labeling(Result).

This doesn't work because #= works only with arithmetic expressions as operands. What are the alternatives to achieve something like this ?

Answer 1

There are many possible ways to model such dependencies with constraints. I consider in this post CLP(FD) and CLP(B) constraints, because they are most commonly used for solving combinatorial tasks.

Consider first CLP(FD), which is more frequently used and more convenient in many ways. When using CLP(FD) constraints, you again have several options to represent your task. However, no matter which model you eventually choose, you must first switch all items in your representation to suitable entitites that the constraint solver can actually reason about. In the case of CLP(FD), this means switching your entities to integers.

Translating your entities to corresponding integers is very straight-forward, and it is one of the reasons why CLP(FD) constraints also suffice to model tasks over domains that actually do not contain integers, but can be mapped to integers. So, let us suppose you are not reasoning about features f1, f2 and f3, but about integers 0, 1, and 2, or any other set of integers that suits you.

You can directly translate your requirements to this new domain. For example, instead of:

[f1,s1] means: f1 needs s1

we can say for example:

0 -> 3 means: 0 needs 3

And this brings us already very close to CLP(FD) constraints that let us model the whole problem. We only need to make one more mental leap to obtain a representation that lets us model all requirements. Instead of concrete integers, we now use CLP(FD) variables to indicate whether or not a specific requirement must be met to obtain the desired features. We shall use the variables R1, R2, R3, ... to denote which requirements are needed, by using either 0 (not needed) or 1 (needed) for each of the possible requirements.

At this point, you must develop a clear mental model of what you actually want to describe. I explain what I have in mind: I want to describe a relation between three things:

1. a list Fs of features
2. a list Ds of dependencies between features and requirements
3. a list Rs of requirements

We have already considered how to represent all these entitites: (1) is a list of integers that represent the features we want to obtain. (2) is a list of F -> R pairs that mean "feature F needs requirement R", and (3) is a list of Boolean variables that indicate whether or not each requirement is eventually needed.

Now let us try to relate all these entitites to one another.

First things first: If no features are desired, it all is trivial:

features_dependencies_requirements([], _, _).

But what if a feature is actually desired? Well, it's simple: We only need to take into account the dependencies of that feature:

features_dependencies_requirements([F|Fs], Ds, Rs) :-
    member(F->R, Ds),

so we have in R the requirement of feature F. Now we only need to find the suitable variable in Rs that denotes requirement R. But how do we find the right variable? After all, a Prolog variable "does not have a bow tie", or—to foreigners—lacks a mark by which we could distinguish it from others. So, at this point, we would actually find it convenient to be able to nicely pick a variable out of Rs given the name of its requirement. Let us hence suppose that we represent Rs as a list of pairs of the form I=R, where I is the integer that defines the requirement, and R is the Boolean indicator that denotes whether that requirement is needed. Given this representation, we can define the clause above in its entirety as follows:

features_dependencies_requirements([F|Fs], Ds, Rs) :-
    member(F->I, Ds),
    member(I=1, Rs),
    features_dependencies_requirements(Fs, Ds, Rs).

That's it. This fully relates a list of features, dependencies and requirements in such a way that the third argument indicates which requirements are necessary to obtain the features.

At this point, the attentive reader will see that no CLP(FD) constraints whatsoever were actually used in the code above, and in fact the translation of features to integers was completely unnecessary. We can as well use atoms to denote features and requirements, using the exact same code shown above.

Sample query and answers:

?- features_dependencies_requirements([f3,f1], 
                                      [f1->s1,f2->s2,f3->s3,f3->s4],
                                      [s1=S1,s2=S2,s3=S3,s4=S4]).
S1 = S3, S3 = 1 ;
S1 = S4, S4 = 1 ;
false.

Obviously, I have made the following assumption: The dependencies are disjunctive, which means that the feature can be implemented if at least one of the requirements is satisifed. If you want to turn this into a conjunction, you will obviously have to change this. You can start by representing dependencies as F -> [R1,R2,...R_n].

Other than that, can it still be useful to translate your entitites do integers? Yes, because many of your constraints can likely be formulated also with CLP(FD) constraints, and you need integers for this to work.

To get you started, here are two ways that may be usable in your case:

• use constraint reification to express what implies what. For example: F #==> R.
• use global constraints like table/2 that express relations.

Particularly in the first case, CLP(B) constraints may also be useful. You can always use Boolean variables to express whether a requirement must be met.