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

 

[Carl Banks]

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
[snip]

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

I would do it in two steps.

Step 1: Generate a graph of all teachers, such that there is one
connection for every four students, and each teacher has approximately
equal number of connections. A simple, approximate way to do this
would be to generate random subsets of two teachers until you have
enough connections (though that won't work well if you have a lot of
teachers that can't work together, which wouldn't be surprising). I'm
sure graph theory has some algorithms to do this if you need more
exactitude.

Step 2: Assign students from appropriate homerooms to each connection.
The following simple algorithm is probably satisfactory: for each
connection between teachers, choose a random subset of four homerooms
not governed by those teachers to form a group. Assign a random
student from each homeroom. Once every student from a homeroom has
been been assigned, remove that homeroom from the set of available
homerooms. With this method, you might have some connections at the
end without enough remaining homerooms; just go fishing for a suitable
switch among students already assigned. Or, work out a way to make
sure you don't exhaust too many homerooms. Perhaps there is a known
algorithm for doing this.

Carl Banks

 

[aurelien.campeas]

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

 

[Steven Bethard]

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
[snip]

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

I would do it in two steps.

Step 1: Generate a graph of all teachers, such that there is one
connection for every four students, and each teacher has approximately
equal number of connections. A simple, approximate way to do this
would be to generate random subsets of two teachers until you have
enough connections (though that won't work well if you have a lot of
teachers that can't work together, which wouldn't be surprising). I'm
sure graph theory has some algorithms to do this if you need more
exactitude.

Step 2: Assign students from appropriate homerooms to each connection.
The following simple algorithm is probably satisfactory: for each
connection between teachers, choose a random subset of four homerooms
not governed by those teachers to form a group. Assign a random
student from each homeroom. Once every student from a homeroom has
been been assigned, remove that homeroom from the set of available
homerooms. With this method, you might have some connections at the
end without enough remaining homerooms; just go fishing for a suitable
switch among students already assigned. Or, work out a way to make
sure you don't exhaust too many homerooms. Perhaps there is a known
algorithm for doing this.

For what it's worth, I went basically this route. My code does
something like:

(1) Generate all pairs of teachers

(2) Remove any pairs of teachers in conflict

(3) Create a list for teacher pairs

(4) Randomly select a teacher pair and add it to the list

(5) If any teachers are at their max number of groups, remove all pairs
that include them from the pairs we are randomly selecting from

(6) If we have not selected a teacher pair for each group, goto (4)

(7) If the resulting graph is disconnected, try again from step (3)

(8) We now have one pair of teachers for each group

(8) Randomly select four other teachers' homerooms for each group

(9) Randomly pop a student off of each homeroom and add it to the group

(10) If a homeroom becomes empty, remove it from the homerooms we are
randomly selecting from.

(11) If at any point we run out of students, try again from step (3)

(12) Eventually, we have assigned people to all teacher-student groups

This seems to work pretty quickly, and doesn't have much trouble finding
solutions to the datasets I've tried it on.

Thanks for your help!

Steve