classroom constraint satisfaction problem
aurelien.campeas@logilab.fr
aurelien.campeas at free.fr
Mon Oct 16 12:50:51 CEST 2006
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: ...
More information about the Python-list
mailing list