Previous Up Next

8.2  Invoking and Using Propia

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.


1
To keep the example simple there is no optimisation.

Previous Up Next