Clpfd reification not working as intended

[David Hernández Morales]

Hello people,

I'm trying to solve a scheduling problem as a personal challenge. I have several subjects, each with different groups that have to fit in a single schedule without overlapping. For this, I define the variables to be 1 hour slots in the timetable and the domains of each variable are the different possible classes to be assigned to that slot. To enforce that each subject must have a single theory group and a single lab group I try to use a reification predicate to forbid assignment of the other groups.

Here are the relevant parts of my code:

writeDomains(VarNumber,[X|Domains]):-
  write('Variable '), write(VarNumber), write(': '),
  write(X), nl,
  VarNumber2 is VarNumber + 1,
  writeDomains(VarNumber2,Domains).


writeDomains(_,[]).


defineVars(Vars):-
  latestStartingHour(N),
  length(Vars,N).


defineDomains([S|Vars],Slot,[L|Tail]):-
  findall([Subject,Group],
  class(Slot,Subject,Group),L),
  length(L,M),
  M >= 1,
  S in 1..M,
  Slot2 is Slot + 1,
  defineDomains(Vars,Slot2,Tail).


defineDomains([S|Vars],Slot,[L|Tail]):-
  findall(Slot,class(Slot,_,_),L),
  length(L,M),
  M =:= 0,
  S in 0,
  Slot2 is Slot + 1,
  defineDomains(Vars,Slot2,Tail).


defineDomains([],_,[]).


defineConstraints(Vars,Domains):-
  onlyOneGroup(Vars,Domains,1).

onlyOneGroup(Vars,Domains,CurrentSubject):-
  numberOfSubjects(N),
  CurrentSubject =< N,
  findall(GTheory,group(CurrentSubject,GTheory,1),LTheory),
  auxOnlyOneGroup(Vars,Domains,CurrentSubject,LTheory),
  findall(GLab,group(CurrentSubject,GLab,0),LLab),
  auxOnlyOneGroup(Vars,Domains,CurrentSubject,LLab),
  Subj2 is CurrentSubject + 1,
  onlyOneGroup(Vars,Domains,Subj2).

onlyOneGroup(_,_,_).

auxOnlyOneGroup(Vars,Domains,CurrentSubject,[G|Groups]):-
  findall(S1,class(S1,CurrentSubject,G),L1),
  findall([S2,G2],(member(G2,Groups),class(S2,CurrentSubject,G2)),L2),
  iterateExclusion(Vars,Domains,CurrentSubject,G,L1,L2),
  auxOnlyOneGroup(Vars,Domains,CurrentSubject,Groups).


auxOnlyOneGroup(_,_,_,[]).


iterateExclusion(Vars,Domains,Subject,G1,[X|RestOfSlots],GroupAndSlot):-
  auxIterate(Vars,Domains,Subject,G1,X,GroupAndSlot),
  iterateExclusion(Vars,Domains,Subject,G1,RestOfSlots,GroupAndSlot).


iterateExclusion(_,_,_,_,[],_).


auxIterate(Vars,Domains,Subj,G1,CurrentSlot,[[S2,G2]|RestOfPairs]):-
  nth1(CurrentSlot,Vars,FirstVar),
  nth1(S2,Vars,SecondVar),
  nth1(CurrentSlot,Domains,FirstList),
  nth1(S2,Domains,SecondList),
  nth1(FirstIndex,FirstList,[Subj,G1]),
  nth1(SecondIndex,SecondList,[Subj,G2]),
  FirstVar #= FirstIndex #==> SecondVar #\=  SecondIndex,
  SecondVar #= SecondIndex #==> FirstVar #\= FirstIndex,
  auxIterate(Vars,Domains,Subj,G1,CurrentSlot,RestOfPairs).


auxIterate(_,_,_,_,_,[]).

The part that isn't working is this one:

FirstVar #= FirstIndex #==> SecondVar #\=  SecondIndex,
SecondVar #= SecondIndex #==> FirstVar #\= FirstIndex,

If you choose the first group, then the second group can't be assigned to that slot and vice versa.

The group predicate simply indicates that a subject has a group and is theoretic or not (1 or 0). And the class predicate is self-explanatory.

When I try to print the variables after being labelled, the onlyOneGroup constraint isn't working because I have a subject with two laboratory groups. 

Can you see what I'm doing wrong?

Thanks in advance,

David.

[Markus Triska]

Hi David,

I have a few comments about this, and I would like to get from most general to more specific issues.

First, reifications often prevent strong propagation, because it is not a priori clear (to the solver) which of the involved constraints hold. For efficient scheduling with CLP(FD), I first recommend you find a model where you can express all constraints directly, i.e., in such a way that each of them always holds. Ideally, global constraints like all_distinct/1 can be used for very strong and efficient pruning.

For example, in your case, what you have done is very natural: Each slot is a variable, and we assign groups or classes to each slot. This is how one would probably intuitively go about finding a solution for such tasks. But, as you note, this requires reifications to express some constraints. So, let us consider a, shall we say, dual view of this: Let us say that each group comes equipped with as many CLP(FD) variables as there are classes for that group. For example, suppose group A must participate in 3 classes: X, Y and Z. (I am not interested in the particular details of this concrete case, but I would like to get the general idea across). Then, you could view the whole task as assigning different slots *to* the variables [X,Y,Z], and that can actually be expressed with all_distinct([X,Y,Z]), yielding very strong propagation.

Thus, first and foremost, I suggest to reconsider how you model this task, and see whether you find a model that does not require reification in the first place.

I have implemented a simple CLP(FD) timetabling engine for schools that worked for sample files I had obtained back then, please have a look:

    https://www.metalevel.at/simsttab/

The source code contains a few comments about the CLP(FD) model.

The second issue I would like to address is the actual problem you are facing: This is very likely due to your use of findall/3. I have not looked into your code in detail, but please note that all-solution predicates do not work nicely with constraints. Please see the manual for more information:

    http://eu.swi-prolog.org/pldoc/man?section=clp

In the timetabling engine I have mentioned above, I am also using all-solution predicates, but never on variables that are involved in constraints!

Thus, if you want to make your existing code work, please try to get rid of the all-solution predicates and express what holds more directly.

Third, I have a few small stylistic suggestions. For example, regarding the first clause of your program:

writeDomains(VarNumber,[X|Domains]):-

  write('Variable '), write(VarNumber), write(': '),

  write(X), nl,

  VarNumber2 is VarNumber + 1,

  writeDomains(VarNumber2,Domains).

you can use format/2 to make this shorter:

writeDomains(VarNumber, [X|Domains]):-

  format('Variable ~w: ~w\n', [VarNumber,X]),

  VarNumber2 #= VarNumber + 1,

  writeDomains(VarNumber2, Domains).

I have also taken the liberty to use the CLP(FD) constraint (#=)/2 instead of (is)/2, to advertise more declarative features. S in 0 is equivalent to S = 0, so you can simply use 0 instead of S where it occurs.

Some of your predicates can likely be written more compactly with foldl/N.

I hope this helps.

All the best!

Markus

[David Hernández Morales]

Alright, I will look into it. Thank you so much for your insight!

[Jan Burse]

Whats the use of (#=)/2 in the below? I don't think he intends
calling format with an unbound VarNumber, so basically

using (#=)/2 in this particular case is nonsense.

[Markus Triska]

Hi Jan,

you are already getting even beyond the recommendations I have suggested! When I wrote them, I left out the following, considering it as not of sufficient interest for the participants at first. However, since you now mention this, let me elaborate:

It is true, nobody intends to call format/2 with an unbound variable. Therefore, I recommend to get rid of the format/2 entirely in this clause, and extend the pure parts of the code, separating it more cleanly from those parts that perform I/O.

For example, in this concrete case, let us consider the following definitions:

    elements_with_indices(Es, EIs) :-

            foldl(element_with_index, Es, EIs, 1, _).

    element_with_index(E, I0-E, I0, I) :-

            I #= I0 + 1.

Now, suppose we have found a fully instantiated solution of the task, i.e., a concrete assignment of variables to values such as [5,4,8,3].

We can equip each of these variables with their index like this:

?- elements_with_indices([5,4,8,3], EIs).

EIs = [1-5, 2-4, 3-8, 4-3].

And now we can get what we originally had like this, using Ulrich Neumerkel's library(lambda):

    ?- elements_with_indices([5,4,8,3], EIs),

       maplist(\ (A-B)^format("variable ~d: ~d\n", [A,B]), EIs).

    variable 1: 5

    variable 2: 4

    variable 3: 8

    variable 4: 3

The advantage is clear: The actual relation between indices and elements can now be effectively tested, because it is cleanly decoupled from side-effects which typically get in the way of testing or even prevent it.

For example, we can now ask what elements with indices look like in general:

    ?- elements_with_indices(Es, EIs).

    Es = EIs, EIs = [] ;

    Es = [_8596],

    EIs = [1-_8596] ;

    Es = [_8596, _8620],

    EIs = [1-_8596, 2-_8620] ;

    Es = [_8596, _8620, _8644],

    EIs = [1-_8596, 2-_8620, 3-_8644] .

This is reassuring, and allows us to easily write unit tests even for such predicates.

All the best!

Markus

[Jan Burse]

The readability of code degenerades considerable in what you are
doing. This is typical Haskell nonsense. As long as you don't have a
double call-pattern (+ = non-var, - = var):

    element_with_index(.., +, -)
  element_with_index(.., -, +)

I don't see any use of using CLP(*). And also then you don't need
CLP(*). Namely you could still do:

    element_with_index(.., I0, I) :- var(IO), !,
       IO is I-1.
  element_with_index(.., IO, I) :-
       I is IO+1.

But then using foldl doesn't work for both direction.
So indeed you need CLP(*) here. Because you will also have
a call mode inbetween:

  element_with_index(.., -, -)

But my advice would be, don't overemphasize CLP(*), maybe
first try to document modes for all of your predicates,
and then if you see you have

some modes that would be apt to CLP(*), only then use
CLP(*). Problem is CLP(*) doesn't work always. These examples
here are some trivial examples where CLP(*) indeeded

works, but there are many many case where CLP(*) can't
do anything.

[Jan Burse]

What would be much more interesting would be a foldl,
that automatically chooses direction, depending on call pattern.

What you call foldl+CLP(*), with a unsuitable pattern, you
do the work twice, what will happen:

   - you call foldl, it will build a CLP constraint chain,
   - and later the last constraint is instantiated
   - and everything propagates back

So from a simple one pass solution, you get to a two pass
solution, with corresponding memory and time overhead

Doesn't make much sense.

[Markus Triska]

Hi Jan, all,

On Wednesday, July 26, 2017 at 9:29:22 PM UTC+2, Jan Burse wrote:

Problem is CLP(*) doesn't work always. These examples
here are some trivial examples where CLP(*) indeeded
works, but there are many many case where CLP(*) can't
do anything.

As the implementor of CLP(FD) in SWI-Prolog, I am especially interested in the latter:

In which cases doesn't CLP(*) work for application programmers in cases they need?

For this reason, I am encouraging the use of CLP(FD) in applications. 

Imagine for a moment that I, the implementor of CLP(FD), posts here what you said: "Maybe first try to document modes for all of your predicates, and then if you see you have some modes that would be apt to CLP(*), only then use CLP(*)."

I leave it to the reader to judge how many applications of CLP(*) this approach would yield over the coming years, and how many opportunities for CLP(FD) improvements we could derive from it.

As I see it: If you are doing integer arithmetic in your programs, try out CLP(FD). That and this sentences is all I have to say on this subject for the moment.

All the best,

Markus

[Jan Burse]

Maybe I should do some measurements (micro or macro benchmarks)
by myself and play around with the idea of another foldl.

This would be something along CLP(FD,L), where L stands
for list (of integers). Anyway:

  An optimist says: The glass is half full.
  A pessimit says: The galss is half empty.
  A programmer says: The glass is twice as large as necessary.
  http://www.hongkiat.com/blog/programming-jokes/

[David Hernández Morales]

Markus, I'm sorry that I didn't answer before, but I was looking at your time table generator and I'm afraid there's a fundamental difference with the one I'm trying to create.

In your generator, you simply have "requirements" of subjects that have to be taken by the students. And you assign these subjects to different slots satisfying a number

of constraints. However, in my generator the subjects have different groups for theory and practice. Each group is already assigned a number of slots. For example.

Subject Algorithms, theory:

• Group 10: Monday 8-10 a.m, Thursday 10-12 a.m
• Group 20: Wednesday 5-7 p.m, Friday 6-8 p.m.

Practice:

• Group 11: Wednesday 3-5 p.m, Friday 5-6 p.m
• Group 12: Monday 8-10 a.m, Tuesday 10-12 a.m

You get the idea. Students are free to choose their groups so the idea is to assign each subject a group so that there is no overlapping between the different subjects and groups. 

Each student must have a single group for theory and a single group for practice. I don't see how to solve this problem with your model because groups have already

assigned slots. I have to assign groups to subjects and I don't think it is possible to enforce consistency across subjects and groups without reification in this case.

Kind regards,

David.

El miércoles, 26 de julio de 2017, 20:08:03 (UTC+2), Markus Triska escribió:

[Markus Triska]

Hi David,

I have not looked into the details of your task, so it can very well be the case that you cannot apply the transformation I have described as an example. Still, the general principle remains: I first recommend to check out alternative models. You may be able to find one where you can express the constraints more directly, or you may not find such a formulation.

If you cannot find such a model with the available constraints, it may be an indication that an important combinatorial constraint is missing from the CLP(FD) implementation. In such cases, the way that historically worked is that other researchers tell me which constraints they need from CLP(FD), and I implement them. In some cases, other CLP(FD) systems may provide a specific constraint that expresses what they want already, so it becomes a matter of studying how other systems work and applying the same principles to the SWI implementation. In other cases, we may have to implement a constraint that is not available in other systems. all_distinct/1 is an example of the former situation, and zcompare/3 is an example of the latter.

I have moved CLP(FD) development to SICStus Prolog, but I still occasionally make improvements to the SWI implementation if the use case is exceptionally interesting. I have always liked timetabling, so...

All the best,

Markus