classroom constraint satisfaction problem

[aurelien.campeas@logilab.fr]

Steven Bethard a écrit :

> 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

Last time I looked at it, it seemed to not use (by default) its Arc8
routine that prunes domains between each variable instantiation by the
backtracker. Did you enable it ? (it should have a crucial performance
impact).

You could also try the logilab constraint package
(http://www.logilab.org/projects/constraint) and see how it fares with
your problem (it 'only' provides the AC3 domain pruning algorithm but
at least uses it by default).

Cheers,
Aurélien.

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