Propia is an ECL^{i}PS^{e}library, 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
9^{3}= 729
alternatives.

If we assume a production batch of *9* units, then the number of
alternative ways of solving `sum`

is
9^{9}
, 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.

- 1
- To keep the example simple there is no optimisation.