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: ... -- http://mail.python.org/mailman/listinfo/python-list
