Modelling in Finite Domains
Domains & Labelling
In finite domain problems, we need to tell the system what the domains of the variables are:
:- use_module(library(fd)).
likes(kim,maria).
likes(kim,nicole).
likes(kim,erika).
likes(peter,maria).
likes(bernd,nicole).
likes(bernd,maria).
likes(bernd,erika).
solved([N,M,E]) :-
[N,M,E] :: [kim,peter,bernd],
N #\= M,
N #\= E,
M #\= E,
likes(N,nicole),
likes(M,maria),
likes(E,erika).
This is what the '::' notation does; in eclipse (but not in clpr), the query
solved(X)
will give rise to the answers
[eclipse 2]: solved(X).
X = [kim, peter, bernd] More? (;)
X = [bernd, peter, kim] More? (;)
yes.
Similarly, we can model the smuggler's knapsack problem with the program
:- use_module(library(fd)).
solved([W,P,C]) :-
[W,P,C] :: [0..9],
4 * W + 3 * P + 2 * C #<= 9,
15 * W + 10 * P + 7 * C #>= 30.
which has the following behaviour:
[eclipse 3]: solved(X).
X = [W{[0..2]}, P{[0..3]}, C{[0..4]}]
Delayed goals:
9 - 2 * C{[0..4]} - 3 * P{[0..3]} - 4 * W{[0..2]}#>=0
-30 + 7 * C{[0..4]} + 10 * P{[0..3]} + 15 * W{[0..2]}#>=0
This is because the eclipse fd solver is incomplete; if we want the solver to fully solve the problem, we need to force backtracking, which in eclipse is provided by the predicate
labeling:[eclipse 4]: solved(X), labeling(X).
X = [0, 1, 3] More? (;)
X = [0, 3, 0] More? (;)
X = [1, 1, 1] More? (;)
etc
We can also use optimization constructs:
:- use_module(library(fd)).
solved([W,P,C]) :-
L #= 15 * W + 10 * P + 7 * C,
minimize(( [W,P,C] :: [0..9],
4 * W + 3 * P + 2 * C #<= 9,
15 * W + 10 * P + 7 * C #>= 30,
labeling([W,P,C])),
L).
behaves as:
[eclipse 2]: solved(X).
Found a solution with cost 31
Found a solution with cost 30
X = [0, 3, 0]
yes.
For another example, the "money" problem:
smm(S,E,N,D,M,O,R,Y) :-
[S,E,N,D,M,O,R,Y] :: [0..9],
constrain(S,E,N,D,M,O,R,Y).
constrain(S,E,N,D,M,O,R,Y) :-
S #\= 0,
M #\= 0,
alldifferent ([S,E,N,D,M,O,R,Y]),
1000*S +100*E +10*N +D
+ 1000*M +100*O +10*R +E
#= 10000*M +1000*O +100*N +10*E +Y.
gives
[eclipse 2]: smm(S,E,N,D,M,O,R,Y).
S = 9
E = E{[4..7]}
N = N{[5..8]}
D = D{[2..8]}
M = 1
O = 0
R = R{[2..8]}
Y = Y{[2..8]}
There are 11 delayed goals. Do you want to see them? (y/n)
Delayed goals:
E{[4..7]} #\= N{[5..8]}
E{[4..7]} #\= D{[2..8]}
E{[4..7]} #\= R{[2..8]}
E{[4..7]} #\= Y{[2..8]}
N{[5..8]} #\= D{[2..8]}
N{[5..8]} #\= R{[2..8]}
N{[5..8]} #\= Y{[2..8]}
D{[2..8]} #\= R{[2..8]}
D{[2..8]} #\= Y{[2..8]}
R{[2..8]} #\= Y{[2..8]}
0-Y{[2..8]}+91*E{[4..7]}
-90*N{[5..8]}+10*R{[2..8]}
+D{[2..8]}#=0
yes.
This arises because the constraint solver is not complete - we need to force backtracking to get a satisfactory answer:
[eclipse 4]: smm(S,E,N,D,M,O,R,Y), labeling([S,E,N,D,M,O,R,Y]).
S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2 More? (;)
yes.
Note that it is usually important for program efficiency for the backtracking predicate to come last:
[eclipse 5]:[S,E,N,D,M,O,R,Y] :: [0..9],
labeling([S,E,N,D,M,O,R,Y]),
smm(S,E,N,D,M,O,R,Y).
eventually gives the same answer, but after some hours, compared to milliseconds.
Complex Constraints
We previously mentioned that use of the built-in complex constraints greatly improves the constraint efficiency
Take the example of liz, fi and sarah playing on a 10 ft seesaw with seats uniformly placed 1ft apart (numbered -5 to 5)
They are to seat themselves so as to be balanced, having weights of 9, 8 and 4 stone respectively
They need room to swing their arms, so must be at least 3 feet apart
We can model this with simple constraints:
:- use_module(library(fd)).
apart(X,Y,N) :-
X #>= Y + N.
apart(X,Y,N) :-
Y #>= X + N.
solve([L,F,S]) :-
[L,F,S] :: [-5..5],
9*L+8*F+4*S #= 0,
apart(L,F,3),
apart(L,S,3),
apart(F,S,3),
labeling([L,F,S]).
giving the behaviour:
[eclipse 2]: solve(X).
X = [4, -2, -5] More? (;)
yes.
This runs quite fast, but larger problems would be slow because of the backtracking involved
A more efficient implementation uses the cumulative predicate:
:- use_module(library(fd)).
:- use_module(library(cumulative)).
apart(X,Y,N) :-
X #>= Y + N.
apart(X,Y,N) :-
Y #>= X + N.
solve([L,F,S]) :-
[L,F,S] :: [-5..5],
9*L+8*F+4*S #= 0,
cumulative([L,F,S],[3,3,3],[1,1,1],1),
labeling([L,F,S]).
with behaviour:
[eclipse 2]: solve(X).
X = [-4, 2, 5]
There are 6 delayed goals. Do you want to see them? (y/n)
More? (;)
yes.
Efficient Labelling
The built-in
labeling predicate generates the elements of the domains in an arbitrary orderingThis is fine if any element of the domain is as good as any other
But often, we may have knowledge about the likely location of solutions in the search space, so we may wish our system to search likely places first
Most finite domain systems provide a number of in-built predicates to facilitate building our own versions of labelling with specific search orders:
%dvar_domain(V,D) returns the list of values D
% in the current domain of variable V
%dom_range(D,Min,Max) returns the minimum and
% maximum values in domain D
We can simulate the basic
labeling predicate using dvar_domain:labeling([]).
labeling([V|Vs]) :-
indomain(V),
labeling(Vs).
indomain(V) :-
dvar_domain(V,D),
member(V,D).
What happens when we apply this in
smm?Recall that the unlabelled version returned:
S = 9
E = E{[4..7]}
N = N{[5..8]}
D = D{[2..8]}
M = 1
O = 0
R = R{[2..8]}
Y = Y{[2..8]}
The call to
labeling([S,E,N,D,M,O,R,Y]) will thus first call indomain(S), which will have no effect since the domain is already a singleton.The next call will be to
indomain(E), first generating E=4, which propagates through to N=5, and then R=8, but then generates dom(D)=[]Backtracking then produces E=5, which successfully propagates through to a solution
Choice of Variable
The backtracking strategy in this particular case works quite well, because the first variables labelled (S, then E) had small domains
But a different choice, eg
labeling([D, R, Y, N, E, S, M, O]) would search less efficientlyIn general, it is better to search the variables with the smallest domains first (the code in the textbook does this for the abstract language CLP(FD)
Eclipse implements a predicate
%deleteff(Var, List, Rest) which returns the Var
% with the smallest domain in List, and the
% Rest of the list
and may be used to implement labelingff (which instantiates the variables, smallest domains first)
Perhaps even more effective is
%deleteffc(Var, List, Rest) which returns the
% Var with the smallest and most constrained % domain in List, and the Rest of the list
Choice of Value
Having chosen a variable to instantiate, what domain value should we try first?
Recall the N-queens problem
Because two queens on the same row will attack each other, and there are as many queens as rows, we know that there is exactly one queen per row
Thus we can represent the problem by simply keeping a list of N variables for the column position of the queen in each row (each variable having the range 1..N)
For large N, it is known that search will be more efficient if it starts from the middle of the domain
But our indomain predicate searches from the smallest to the largest
The predicate indomain_middle in the text re-orders the domain to work outwards from the middle
Tabular results in the text show that sensible choice of variable gives almost two orders of magnitude speed-up on N queens; value ordering has higher start-up costs, but by the time the count has reached 100 queens, there is a further order of magnitude speed-up
Domain Splitting
You can think of labelling as adding an extra constraint to a problem to test out if it leads to a solution
But thought of in this way, why should we limit ourselves to constraints of the form X=value?
In particular, rather than trying just one value for X, why not try a range of values?
The most obvious approach is to split the domain for X in half, and try (say) the lower range for X first, backtracking to the upper range
If unsatisfiability is detected, we have removed from consideration half of Xs range, not just a single value
The text details how to do this in CLP(FD)
In eclipse, we would make use of the predicates
%dvar_remove_smaller(DVar, El)
% Remove all elements in the domain of DVar
% which are smaller than the integer El
%dvar_remove_larger(DVar, El)
% Remove all elements in the domain of DVar
% which are larger than the integer El
Problem Modellings
Omitted
Extended Example
Omitted
Arc Consistency
Omitted
Reified Constraints
Omitted