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...dent_groups.py
... _tests:

http://ucsu.colorado.edu/~bethard/py...dent_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: ...