The Role of Propia and CHR in Problem Modelling

15.2 The Role of Propia and CHR in Problem Modelling

To formulate and solve a problem in ECLⁱPS^e the standard pattern is as follows:

Initialise the problem variables
State the constraints
Specify the search behaviour

Very often, however, the constraints involve logical implications or disjunctions, as in the case of the noclash constraint above. Such constraints are most naturally formulated in a way that would introduce choice points during the constraint posting phase. The two ECLⁱPS^e clauses defining noclash, above, are a case in point.

There are two major disadvantages of introducing choice points during constraint posting:

Posting and reposting constraints during search is an unnecessary and computationally expensive overhead
Mixing constraint behaviour and search behaviour makes it harder to explore and optimize the algorithm executed by the program.

Propia and CHR’s support the separation of constraint setup and search behaviour, by allowing constraints to be formulated naturally without their execution setting up any choice points.

The effect on performance is illustrated by the following small example. The aim is to choose a set of 9 products (Products, identified by their product number 101-109) to manufacture, with a limited quantity of raw materials (Raw1 and Raw2), so as to achieve a profit (Profit) of over 40. The amount of raw materials (of two kinds) needed to produce each product is listed in a table, together with its profit.

product_plan(Products) :-
    length(Products,9),
    Raw1 #=< 95,
    Raw2 #=< 95,
    Profit #>= 40,
    sum(Products,Raw1,Raw2,Profit),
    labeling(Products).

product( 101,1,19,1).  product( 102,2,17,2).  product( 103,3,15,3).
product( 104,4,13,4).  product( 105,10,8,5).  product( 106,16,4,4).
product( 107,17,3,3).  product( 108,18,2,2).  product( 109,19,1,1).

sum(Products,Raw1,Raw2,Profit) :-
    ( foreach(Item,Products),
      foreach(R1,R1List),
      foreach(R2,R2List),
      foreach(P,PList)
    do
        product(Item,R1,R2,P)
    ),
    Raw1 #= sum(R1List),
    Raw2 #= sum(R2List),
    Profit #= sum(PList).

The drawback of this program is that the sum constraint calls product which chooses an item and leaves a choice point at each call. Thus the setup of the sum constraint leaves 9 choice points. Try running it, and the program fails to terminate within a reasonable amount of time.

Now to make the program run efficiently, we can simply annotate the call to product as a Propia constraint making: product(Item,R1,R2,P) infers most. This program leaves no choice points during constraint setup, and finds a solution in a fraction of a second.

In the remainder of this chapter we show how to use Propia and CHR’s, give some examples, and outline their implementation.

Propia and CHRs can be used to build clear problem models that have no (hidden) choice points.

Figure 15.2: Modelling without Choice Points