classroom constraint satisfaction problem

[Carl Banks]

Steven Bethard wrote:
> 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