classroom constraint satisfaction problem

[Steven Bethard]

I'm trying to solve a constraint-satisfaction problem, and I'm having 
some troubles framing my problem in such a way that it can be 
efficiently solved.

Basically, I want to build groups of two teachers and four students such 
that [1]:

* Students are assigned to exactly one group
* Teachers are assigned to approximately the same number of groups
* Students are not in groups with their homeroom teachers
* Students in each group are from four different homerooms

So given teachers A, B, C, D, E and F and their corresponding students 
A1, A2, ... F3, F4, here's a good grouping:

A, B:   C1, D1, E1, F1
B, C:   A1, D2, E2, F2
C, D:   A2, B1, E3, F3
D, E:   A3, B2, C2, F4
E, F:   A4, B3, C3, D3
F, A:   B4, C4, D4, E4


My current solution is to create a constraint satisfaction problem using 
python-constraint (http://labix.org/python-constraint) where there are 
variables for:

* each student      domain: group names
* each group name   domain: all pairs of teachers

This works for simple problems, but because most of my constraints have 
to iterate over all students and/or all groups, this takes way too long 
on my real dataset (which has 300+ students).  I thought about trying to 
reframe the problem so that there are variables for:

* each group name   domain: pairs of teachers X 4-tuples of students

but that seems like it would be generating something like 15^2*300^4 
items for the domain, which is clearly also going to be way too big.


Any suggestions on how to speed things up?  I've posted my current code_ 
and the tests_ in case anyone has the time to look at them.

.. _code: http://ucsu.colorado.edu/~bethard/py/constraint/student_groups.py
.. _tests:
http://ucsu.colorado.edu/~bethard/py/constraint/test_student_groups.py


Thanks!

Steve


[1] There are actually two other constraints that I omitted:

* Some teachers cannot be placed in the same group, e.g. I might know 
that A cannot work with B or that E cannot work with F.

* If you create a graph out of the teacher pairs from all the groups, 
the graph should not be disconnected.  That is, the following grouping 
is bad because the teachers are disconnected:

A, B: ...
C, D: ...
A, B: ...

while this grouping would be okay:

A, B: ...
B, C: ...
C, D: ...