Previous Up Next

11.5  Rules for Modelling Code

In CLP, the declarative model is at the same time the constraint setup code. This code should therefore be deterministic and terminating, so:

Careful with disjunctions
Don’t leave choice-points (alternatives for backtracking). Choices should be deferred until search phase.
Use only simple conditionals
Conditions in (...->...;...) must be true or false at modelling time!
Use only structural recursion and loops
Termination conditions must be know at modelling time!

11.5.1  Disjunctions

Disjunctions in the model should be avoided. Assume that a naive model would contain the following disjunction:

no_overlap(S1,D1,S2,D2) :- S1 #>= S2 + D2.
no_overlap(S1,D1,S2,D2) :- S2 #>= S1 + D1.

There are two basic ways of treating the disjunction:

In the example, we can introduce a boolean variable B{0,1} which represents the choice. The actual choice can be then be taken in search code by choosing a value for the variable. The model code must then be changed to observe the decision variable, either using the delay facility of ECLiPSe:

delay no_overlap(S1,D1,S2,D2,B) if var(B).
no_overlap(S1,D1,S2,D2,0) :- S1 #>= S2 + D2.
no_overlap(S1,D1,S2,D2,1) :- S2 #>= S1 + D1.

or using an arithmetic encoding like in

no_overlap(S1,D1,S2,D2,B) :-
        B :: 0..1, 
        S1 +     B*1000 #>= S2 + D2,
        S2 + (1-B)*1000 #>= S1 + D1.

The alternative of turning the disjunction into a proper constraint is achieved most easily using propia’s infer-annotation (see 15). The original formulation of neighbour/2 is kept but it is used as follows:

    ..., no_overlap(S1,D2,S2,D2) infers most, ...

11.5.2  Conditionals

Similar considerations apply to conditionals where the condition is not decidable at constraint setup time. For example, suppose we want to impose a no-overlap constraint only if two tasks share the same resource. The following code is currently not safe in ECLiPSe:

nos(Res1, Res2, Start1, Dur1, Start2, Dur2) :-
    ( Res1 #= Res2 ->           % WRONG!!!
        no_overlap(Start1, Dur1, Start2, Dur2)

The reason is that (at constraint setup time) Res1 and Res2 will most likely be still uninstantiated. Therefore, the condition will in general delay (rather than succeed or fail), but the conditional construct will erroneously take this for a success and take the first alternative.

Again, this can be handled using delay

delay nos(Res1, Res2, _, _, _, _) if nonground([Res1,Res2]).
nos(Res1, Res2, Start1, Dur1, Start2, Dur2) :-
    ( Res1 == Res2 ->
        no_overlap(Start1, Dur1, Start2, Dur2)

It might also be possible to compute a boolean variable indicating the truth of the condition. This is particularly easy when a reified constraint can be used to express the condition, like in this case:

nos(Res1, Res2, Start1, Dur1, Start2, Dur2) :-
    #=(Res1, Res2, Share),
    cond_no_overlap(Start1, Dur1, Start2, Dur2, Share).

delay cond_no_overlap(_,_,_,_,Share) if var(Share).
cond_no_overlap(Start1, Dur1, Start2, Dur2, Share) :-
    ( Share == 1 ->
        no_overlap(Start1, Dur1, Start2, Dur2)

Previous Up Next