Propia is an ECLiPSelibrary, loaded by calling
?- lib(propia).
A goal, such as member(X,[1,2,3]), is turned into a constraint
by annotating it using the infers operator.
The second argument of infers defines how much propagation
should be attempted on the constraint and will be described in
section 8.3 below.
In this section we shall use Goal infers most, which infers as
much information as possible, given the loaded constraint solvers. If
the IC solver is loaded, then IC information is
extracted, and Propia reduces the domains to achieve arc-consistency.
We first show the behaviour of the original goal:
?- member(X, [1, 2, 3]). X = 1 Yes (0.00s cpu, solution 1, maybe more) X = 2 Yes (0.02s cpu, solution 2, maybe more) X = 3 Yes (0.02s cpu, solution 3)
Constraint propagation is invoked by infers most:
?- lib(ic).
...
?- member(X, [1, 2, 3]) infers most.
X = X{1 .. 3}
Yes (0.00s cpu)
Note that the information produced by the constraint solves the corresponding goal as well. The constraint can thus be dropped.
In case there remains information not yet extracted, the constraint must delay so that completeness is preserved:
?- member(X,Y) infers most.
X = X
Y = [H3|T3]
Delayed goals:
member(X, [H3|T3]) infers most
yes.
Propia copes correctly with built-in predicates, such as #>and #<, so after compiling this simple program:
notin3to6(X) :- X#<3. notin3to6(X) :- X#>6.
the predicate can be used as a constraint:
?- X :: 1 .. 10, notin3to6(X) infers most.
X = X{[1, 2, 7 .. 10]}
Yes (0.00s cpu)
In this example there are no “delayed” constraints since all valuations for X satisfying the above conditions are solutions. Propia detects this and therefore avoids delaying the constraint again.
In scheduling applications it is necessary to constrain two tasks that require the same machine not to be performed at the same time. Specifically one must end before the other begins, or vice versa. If one task starting at time ST1 has duration D1 and another task starting at time ST2 has duration D2, the above “disjunctive” constraint is expressed as follows:
noclash(ST1,D1,ST2,D2) :- ST1 #>= ST2+D2. noclash(ST1,D1,ST2,D2) :- ST2 #>= ST1+D1.
Generalised Propagation on this constraint allows useful information to be extracted even before it is decided in which order the tasks should be run:
?- lib(ic).
...
?- [ST1, ST2] :: 1 .. 10, noclash(ST1, 5, ST2, 7) infers most.
ST1 = ST1{[1 .. 5, 8 .. 10]}
ST2 = ST2{[1 .. 3, 6 .. 10]}
There is 1 delayed goal.
Yes (0.00s cpu)
The values 6 and 7 are removed from the domain of ST1 because
the goal noclash(ST1,5,ST2,7) cannot be satisfied if ST1 is
either 6 or 7. For example if ST1 is 6, then either
6>ST2+7 (to satisfy the first clause defining noclash)
or else ST2>6+5 (to satisfy the second clause). There is no value for
ST2 in {1...10} that makes either inequality true, and so 6 is
removed from the domain of ST1. By a similar reasoning
4 and 5 are removed from the domain of ST2.
We next take a simple example from propositional logic. In this example the result of constraint propagation is reflected not only in the variable domains, but also in the unification of problem variables. We first define logical conjunction by its truth table:
land(true,true,true). land(true,false,false). land(false,true,false). land(false,false,false).
Now we ask for an X,Y,Z satisfying
land(X,Y,Z) ∧ X=Y.
Both solutions have X=Y=Z, and this information is produced solely
by propagating on the land constraint:
?- land(X, Y, Z) infers most, X = Y. Z = X X = X Y = X There is 1 delayed goal. Yes (0.00s cpu)
We now illustrate the potential efficiency benefits of Generalised Propagation with a simple resource allocation problem. A company makes 9 products, each of which require two kinds of components in their manufacture, and yields a certain profit. This information is held in the following table.
/*** product(Name,#Component1,#Component2,Profit). **/ product(1,1,19,1). product(2,2,17,2). product(3,3,15,3). product(4,4,13,4). product(5,10,8,5). product(6,16,4,4). product(7,17,3,3). product(8,18,2,2). product(9,19,1,1).
We wish to find which products to manufacture in order to make a certain profit without using more than a certain number of either kind of component.1
We first define a predicate sum(Products,Comp1,Comp2,Profit)
which relates a list of products (eg Products=[1,5,1]),
to the number of each component required to build all the products in the list
and the profit
(for [1,5,1], Comp1=12 and Comp2=46 and
Profit=7).
sum([],0,0,0).
sum([Name|Products],Count1,Count2,Profit) :-
[Count1,Count2,Profit]::0..100,
product(Name,Ct1a,Ct2a,Profita),
Count1 #= Ct1a+Ct1b,
Count2 #= Ct2a+Ct2b,
Profit #= Profita+Profitb,
sum(Products,Ct1b,Ct2b,Profitb).
If sum is invoked with a list of variables as its first argument,
eg [V1,V2,V3], then the only choice made during execution is at
the call to product. In short, for each variable in the input
list there are 9 alternative products that could be chosen.
For a list of three variables there are consequently
93= 729
alternatives.
If we assume a production batch of 9 units, then the number of
alternative ways of solving sum is
99
, or nearly 400
million. To avoid exploring so many possibilities, we simply annotate
the call to product(Name,Ct1a,Ct2a,Profita) as a Generalised
Propagation constraint.
Thus the new definition of sum is:
sum([],0,0,0).
sum([Name|Products],Count1,Count2,Profit) :-
[Count1,Count2,Profit]::0..100,
product(Name,Ct1a,Ct2a,Profita) infers most,
Count1 #= Ct1a+Ct1b,
Count2 #= Ct2a+Ct2b,
Profit #= Profita+Profitb,
sum(Products,Ct1b,Ct2b,Profitb).
Now sum refuses to make any choices:
?- sum([V1, V2, V3], Comp1, Comp2, Profit).
V1 = V1{1 .. 9}
V2 = V2{1 .. 9}
V3 = V3{1 .. 9}
Comp1 = Comp1{3 .. 57}
Comp2 = Comp2{3 .. 57}
Profit = Profit{3 .. 15}
There are 9 delayed goals.
Yes (0.01s cpu)
Using the second version of sum,
it is simple to write a program which produces lists of products
which use less than a given number Max1 and Max2 of each
component, and yields more than a given profit MinProfit:
solve(Products,Batch,Max1,Max2,MinProfit) :-
length(Products,Batch),
Comp1 #=< Max1,
Comp2 #=< Max2,
Profit #>= MinProfit,
sum(Products,Comp1,Comp2,Profit),
labeling(Products).
The following query finds which products to manufacture in order to make a profit of 40 without using more than 95 of either kind of component.
?- solve(P, 9, 95, 95, 40). P = [1, 4, 5, 5, 5, 5, 5, 5, 5] Yes (0.03s cpu, solution 1, maybe more)
Constraints can be dropped as soon
as they became redundant (i.e. as soon as they were entailed by the
current partial solution).
The check for entailment can be expensive, so Propia only drops
constraints if a simple syntactic check allows it.
For infers most, this check succeeds if the IC
library is loaded, and the constraint has only one remaining variable.