.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Declarative Programming
More on Finite Domains
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reasoning about domains
▶ So far, we have covered the establishment of integer finite
domains for variables, and how they can be programmed
at the object level
▶ It is possible, however, to ask questions about the
domains themselves, using meta-predicates
▶ For example, we can ask what is the minimum possible
value of a domain at any given time:
?- X in 1..10, X #\= 1, fd_inf( X, Min ).
Min = 2
X in 2..10 ?
true
▶ This is useful when we want to forcibly minimise a value
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reasoning about domains (2)
▶ We can ask about the size of a domain:
?- X in 1..10, X in 5..15,
fd_size( X, Size ).
Size = 6
X in 5..10 ?
true
▶ This is useful when we want to constrain search by
instantiating the variable with the smallest domain first
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reasoning about domains (3)
▶ And we can get at the whole domain (in two ways), in
case we want to do some more subtle search control:
?- X in 1..10, X #\= 5,
fd_dom( X, Dom ).
Dom = (1..4)\/(6..10)
X in (1..4)\/(6..10) ?
true
▶ All these predicates are used to implement the
labeling/2 predicate
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Labelling variables
▶ The predicate labeling/2 (note the American spelling)
is a fast way of “filling the gaps” in a constraint system
involving many variables
▶ Of course, not all constraint systems have a unique
solution, and we need a way of choosing values
▶ One other way is to use indomain/1, but this only works
for one variable at a time
▶ labeling/2 takes arguments as follows:
1. A control specification;
2. A list of variables to be given values
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Labelling variables (2)
▶ The control specification consists of three parts:
Variable choice heuristic – in which order to instantiate
variables;
Value choice heuristic – how to search through the
possible values;
Optimality – all solutions, or just one optimal one.
▶ We can use these options to improve our search,
depending on what we know about the distributions of
the solutions about the domains
▶ Sometimes, they can make a considerable improvement,
particularly when many inequalities are involved; however,
sometimes, as in the fd_adder example, they make
things worse
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Labelling variables (3)
▶ Two particularly useful options are maximize and
minimize (again, note the spelling)
▶ They tie a variable to its maximum (minimum) possible
value as the labelling is generated eg
% without labelling
?- X in 1..10, Y in 2..8, X #< Y + 2.
X in 1..9,
Y in 2..8 ?
true
% with labelling
?- X in 1..10, Y in 2..15, X #< Y + 2,
labeling( [max(X)], [X,Y] ).
X = 10,
Y = 9 ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Labelling variables (4)
▶ We can maximize more than one variable:
?- X in 1..10, Y in 2..15, X #< Y + 2,
labeling( [max(X),max(Y)],
[X,Y] ).
X = 10,
Y = 15 ? ;
false
Note that the variable named last is the one to be
maximized.
▶ Note that when we use optimisation, we only get one
solution
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Labelling variables (5)
▶ In some constraint systems, we can maximise more than
one variable; the order in which variables are maximised
can affect their values
▶ To see why, consider each variable as one of a number of
dimensions defining a multi-dimensional space
▶ The domains of the variables demarcate a hyper-solid in
that space, in the body of which solutions may lie
▶ The hyper-solid may have local maxima and minima with
respect to some dimensions which are not global
▶ This constraint system will try to explore all the maxima
and minima on backtracking
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: resource allocation
▶ Suppose we have to design a simple program for stock
control:
▶ We have a number of boxes to stack in a restricted space.
All the boxes are of the same width and depth, but their
heights vary.
▶ The largest boxes contain the heaviest goods, and so
should be stacked lowest
▶ The space available is big enough for 1 box deep (4 units),
and 4 boxes along (16 units), but it is only 8 units high.
▶ How can we stack the boxes to make them fit?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: resource allocation (2)
▶ Our box sizes can be represented like this:
% box( number, height )
:- block box( -, - ).
box( 1, 2 ).
box( 2, 2 ).
box( 3, 6 ).
box( 4, 2 ).
box( 5, 4 ).
box( 6, 2 ).
box( 7, 6 ).
box( 8, 5 ).
box( 9, 3 ).
▶ box/2 is blocked to prevent too-early choice of box and
height
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: resource allocation (3)
▶ We can constrain the physical properties of individual
boxes like this:
constrain_boxes( [], [], [] ).
constrain_boxes( [Box|Boxes],
[B,T,Stack|Variables],
[box( Box,B,T,H,Stack )
|BoxList] ) :-
box( Box, H ),
space( _MaxWidth, MaxHeight ),
T in 0..MaxHeight,
B in 0..MaxHeight,
H in 2..6,
T #= B + H,
Stack in 1..4,
constrain_boxes( Boxes,
Variables, BoxList ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: resource allocation (4)
▶ We can constrain the relationships between boxes like
this:
link_boxes( [] ).
link_boxes( [_] ).
link_boxes( [box( _, _, T1, H1, Stack1 ),
box( Box2, B2, T2, H2, Stack2 )|Boxes] ) :-
Stack2 #>= Stack1,
Stack2 #=< Stack1 + 1,
( Stack1 #= Stack2 ) #==> ( H1 #>= H2 ),
( Stack1 #= Stack2 ) #<==> ( T1 #= B2 ),
( Stack1 #= Stack2 – 1 ) #<==> ( B2 #= 0 ),
link_boxes( [box( Box2, B2, T2, H2, Stack2 )|
Boxes] ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Example: resource allocation (5)
▶ We link the two together like this:
store_boxes( BoxList ) :-
length( BoxList, 9 ),
length( BoxNumbers, 9 ),
all_different( BoxNumbers ),
constrain_boxes( BoxNumbers, Variables,
BoxList ),
link_boxes( BoxList ),
labeling( [ffc], Variables ).
▶ And we get a solution:
X = [box(5,0,4,4,1),box(1,4,6,2,1),
box(2,6,8,2,1),box(8,0,5,5,2),
box(9,5,8,3,2),box(3,0,6,6,3),
box(4,6,8,2,3),box(7,0,6,6,4),
box(6,6,8,2,4)] ?