Skip to first unread message

Jul 26, 2017, 12:45:19 PM7/26/17

to SWI-Prolog

Hello people,

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

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,

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.

Jul 26, 2017, 2:08:03 PM7/26/17

to SWI-Prolog

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:

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:

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

Jul 26, 2017, 2:44:49 PM7/26/17

to SWI-Prolog

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

Jul 26, 2017, 2:49:38 PM7/26/17

to SWI-Prolog

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.

calling format with an unbound VarNumber, so basically

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

Jul 26, 2017, 3:07:21 PM7/26/17

to SWI-Prolog

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

Jul 26, 2017, 3:29:22 PM7/26/17

to SWI-Prolog

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.

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.

Jul 26, 2017, 3:40:54 PM7/26/17

to SWI-Prolog

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.

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.

Jul 26, 2017, 3:41:55 PM7/26/17

to SWI-Prolog

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

Jul 26, 2017, 3:55:38 PM7/26/17

to SWI-Prolog

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/

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/

Jul 27, 2017, 10:24:51 AM7/27/17

to SWI-Prolog

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.

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

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ó:

Jul 27, 2017, 10:40:59 AM7/27/17

to SWI-Prolog

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu