Rules for Modelling Code

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:

% DO NOT USE THIS IN A MODEL
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:

Deferring the choice until the search phase by introducing a decision variable.
Changing the behaviour of the disjunction so it becomes a constraint (see also 14 and 15).

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 ECLⁱPS^e:

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)
    ;
        true
    )

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)
    ;
        true
    ).

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)
    ;
        true
    ).