Prolog: foreach or forall for constraint solving?

Question

I'm attempting project scheduling with SWI prolog and CLP. I managed to support sequential dependencies but I'm struggling with avoiding double booking people.

I have a list called Schedule containing elements like [taskname, starttime] where starttime is a free variable for the constraint solver. They're already constrained by sequential dependencies.

I'm trying to write a loop like this to rule out double bookings:

  forall /* or maybe foreach*/ (isa(P,person), (
    % Filter scheduled tasks on that person...
    include(\[T,S]^(assigned(T,P)), Schedule, HisSchedule),
    % Present what serialized expects..
    maplist(\[T,S]^S^true, HisSchedule, Sts),
    % duration is just user-defined data... 
    maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
    % Hit it...
    serialized(Sts, Dus)
  )),

With foreach it always fails and with forall it always succeeds without constraining anything.

Schedule is global as far as this loop is concerned, and the purpose is to constrain its starttime elements using serialized. OTOH, HisSchedule, Sts and Dus depend on the particular person. So I think I need foreach to make Schedule happy but forall to make HisSchedule etc happy. Is that the problem? And if so how do I fix it?

Note that the standard definition of the `forall/2` predicate is: `forall(Generator, Test) :- \+ (Generate, \+ Test)`. The use of negation (as failure) is likely the reason why your query succeeds without constraining anything. — Paulo Moura, Nov 15 '14 at 15:17

score 8 · Accepted Answer · edited Jun 20 '20 at 09:12

The forall/2 built-in is offered by some Prolog systems, it relies heavily on non-monotonic constructs, and was never designed to collaborate with constraints. Same is true for foreach/2 which attempts to be a bit smarter.

Answers, solutions, constraints

So, what is the big, fundamental problem here? A lot of Prolog received its current form when constraints were not widely known. Many constructs thus take success of a goal as a yes as ultimate truth. But with constraints, things are a bit different. A succeeding goal produces an answer which now may contain no solution at all! For this reason success is not what it used to be. Here is an example using SICStus:

| ?- asserta(clpfd:full_answer).
yes
| ?- X mod 2 #= 1.
clpfd:(X mod 2#=1),
X in inf..sup ? 
yes
| ?- X mod 2 #= 1, X mod 2 #= 0.
clpfd:(X mod 2#=0),
clpfd:(X mod 2#=1),
X in inf..sup ? ;
no
| ?- X mod 2 #= 1, X mod 2 #= 0, X in 0..9.
no

Answers may now contain no solution at all, in other words, they may be false.

In your example include/3 is highly problematic, as is forall/2. Ah, and also setof/3 gets crazy with constraints:

| ?- setof(t, (I in 1..3 ; I in 3..5 ), _). % SICStus
yes

?- setof(t, (I in 1..3 ; I in 3..5 ),_).  % SWI
I = 3.

If at all, the correct answer would be I in 1..5.

To solve this problem, first transform the relational data into lists:

   ...,
   setof(P, isa(P, person), Ps),
   maplist(perperson(P,Global),Ps),
   ...

Thanks for this. Just out of interest, do you know any good material about how to do resource planning with CLP? I'm dreading the bit where I consider splitting tasks around e.g. holidays or other high priority tasks and represent the time lost when the worker changes subject. At that point, there's no longer a simple start, duration and end. — Adrian May, Nov 16 '14 at 07:25
@AdrianMay: Maybe start with [this](http://logic.at/prolog/simsttab/simsttab.html) — false, Nov 16 '14 at 09:41

score 2 · Answer 2 · answered Nov 16 '14 at 07:18

2

I fixed it myself like this:

  findall(Per, isa(Per,person), People),
  maplist(nodoublebookings(Schedule),People),

nodoublebookings(Schedule, Per):-
  include(\[T,S]^(assigned(T,Per)), Schedule, HisSchedule),
  maplist(\[T,S]^S^true, HisSchedule, Sts),
  maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
  serialized(Sts, Dus).

For some reason I couldn't write nodoublebookings as a lambda.

answered Nov 16 '14 at 07:18

Adrian May

2,127
15
24

Using `findall/3` instead of `setof/3` means that accidental changes in the sequence of solutions may change the way how the problem is solved. – false Nov 16 '14 at 09:42
1

`..., maplist(Schedule+\Per^( include ... ), People), ...` by default, variables are local to the `\`, you need to declare those that are not. – false Nov 16 '14 at 09:44

Prolog: foreach or forall for constraint solving?

2 Answers2

Answers, solutions, constraints

Linked