[eclipse-clp-users] Constraint limits and Timetabling?

From: Seppe vanden Broucke <macuyiko_at_gmail.com>
Date: Wed, 5 Aug 2009 16:00:10 +0200
Hi, I'm just getting started with Eclipse (and Prolog in general), and
it looks like a powerful (but quite difficult) package.
I'm trying to solve a time tabling problem. For example, I have this
timetable for two teams of chess players, both containing 5 members:

  1  2  3  4  5
1 A     B  C
2    D  E
3          F  G
4    H  I     J
5 K        L

Players can choice who they want to play against, once that is done, I
want to assign a timeslot to each game (letter), and this in minimal
time (in this case, 3 timeslots).
There are some other constraints: the timeslots in each row and in
each column have to be different.
And, for the members of team A (let's say the rows), I don't want them
to wait between games. So - in this case - I don't want someone with
two games to get timeslots '1' and '3'.

My program now looks like this:

:- lib(ic).

solve(Games) :-
	Games = [A,B,C,D,E,F,G,H,I,J,K,L],
	Games :: [1..3], %3 timeslots
	
	% Constraints - rows
	A #\= B, B #\= C, C #\= A,
	D #\= E,
	F #\= G,
	H #\= I, I #\= J, J #\= H,
	K #\= L,
	
	% Constraints - cols
	A #\= K,
	D #\= H,
	B #\= E, E #\= I, I #\= B,
	C #\= F, F #\= L, L #\= C,
	G #\= J,
	
	% Constraints - no waiting
	A + B + C #= 6,
	H + I + J #= 6,
	D + E #= 3 or D + E #= 5,
	F + G #= 3 or F + G #= 5,
	K + L #= 3 or K + L #= 5,
	
	% Search
	labeling(Games).

Which is pretty horrible, how can I solve following problems:
1) Less constraints. When I apply this scenario to two teams of 200
participants each, having e.g. 20000 (200^2/2) games, Eclipse crashes.
TkEclipse closes when I compile the program, and DosEclipse puts me
back to the command prompt without any warning. I've also tried
increasing the stack size. The problem lies (I think) with having to
much constraints (when I remove enough of them, the file compiles).
Alas I cannot give an error message, since there was nothing displayed
(see output at the end of this message).
1a) I guess for the rows and columns I can use alldifferent(). Can I
just use alldifferent([B,I,E]) in this case?
1b) Setting up the no waiting constraint is a bit harder. Is there a
better way to enforce this instead of going over every possibility and
'or'-ing them together?

Thanks in advance,
Seppe



------- output -------
c:\Installed Files\Eclipse 6.0\lib\i386_nt>eclipse.exe
ECLiPSe Constraint Logic Programming System [kernel]
Kernel and basic libraries copyright Cisco Systems, Inc.
and subject to the Cisco-style Mozilla Public Licence 1.1
(see legal/cmpl.txt or www.eclipse-clp.org/licence)
Source available at www.sourceforge.org/projects/eclipse-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.0 #96 (i386_nt), Wed Jul 22 01:05 2009
[eclipse 1]: cd('C:\\Users\\Seppe\\Desktop').

Yes (0.00s cpu)
[eclipse 2]: compile('a3.ecl').
source_processor.eco loaded in 0.02 seconds
hash.eco   loaded in 0.02 seconds
compiler_common.eco loaded in 0.03 seconds
compiler_normalise.eco loaded in 0.00 seconds
compiler_map.eco loaded in 0.00 seconds
compiler_analysis.eco loaded in 0.02 seconds
compiler_peephole.eco loaded in 0.02 seconds
compiler_codegen.eco loaded in 0.01 seconds
compiler_varclass.eco loaded in 0.02 seconds
compiler_indexing.eco loaded in 0.02 seconds
compiler_regassign.eco loaded in 0.00 seconds
asm.eco    loaded in 0.02 seconds
module_options.eco loaded in 0.00 seconds
ecl_compiler.eco loaded in 0.17 seconds
ic_kernel.eco loaded in 0.02 seconds
linearize.eco loaded in 0.00 seconds
ic_constraints.eco loaded in 0.03 seconds
ic.eco     loaded in 0.00 seconds
ic_generic_interface.eco loaded in 0.00 seconds
ic_search.eco loaded in 0.02 seconds
ic.eco     loaded in 0.08 seconds

c:\Installed Files\Eclipse 6.0\lib\i386_nt>
Received on Wed Aug 05 2009 - 14:00:43 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET