classroom constraint satisfaction problem

Discussion in 'Python' started by Steven Bethard, Oct 15, 2006.

  1. 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: ...
    Steven Bethard, Oct 15, 2006
    #1
    1. Advertising

  2. Steven Bethard

    Carl Banks Guest

    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
    Carl Banks, Oct 16, 2006
    #2
    1. Advertising

  3. Steven Bethard

    Guest

    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: ...
    , Oct 16, 2006
    #3
  4. Carl Banks wrote:
    > Steven Bethard wrote:
    >> 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
    Steven Bethard, Oct 24, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Secure Futures

    Achieve Freedom, Satisfaction & Success!

    Secure Futures, Jun 15, 2004, in forum: HTML
    Replies:
    0
    Views:
    409
    Secure Futures
    Jun 15, 2004
  2. John Carson
    Replies:
    1
    Views:
    2,585
    Dan Cernat
    Jan 7, 2004
  3. Bruce Lee 646
    Replies:
    2
    Views:
    443
    loupceuxl
    Jan 31, 2005
  4. Replies:
    0
    Views:
    362
  5. puvit82
    Replies:
    4
    Views:
    760
    puvit82
    Feb 1, 2008
Loading...

Share This Page