Author Topic: Algorithm help needed  (Read 2964 times)

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Algorithm help needed
« on: June 21, 2011, 10:29:52 AM »
This is a work project.  We've got a set of students that we need to assign to a teacher (from a set of teachers).  For each student we there is a subset of allowable teachers.  There is a function that gives each possible student-teacher combo a score.  What I need to do now is assign the student to the teacher while minimizing the total score for each teacher while keeping the total scores for all teachers balanced.  There is also a restriction on the number of students a particular teacher can be assigned.  While I'm going to ignore it in the initial attempt there are also preassigned students who can not be moved to another teacher.

Now I don't really need help with the algorithm per se, what I need help with is figuring out which classic algorithm that mirrors.  I know it does but it is in that deep recesses of my memory of a badly taught class.

charlie

  • Jackass In Charge
  • Posts: 7896
  • Karma: +84/-53
Re: Algorithm help needed
« Reply #1 on: June 21, 2011, 11:25:38 AM »
Knapsack?


Shoot I don't remember anything from that class, even though I aced it despite only showing up a handful of times.

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #2 on: June 21, 2011, 11:29:30 AM »
Knapsack is what I was thinking also but when I re-read the wiki article I'm not sure.  It is almost like I've got a pool of things to fill multiple knapsacks.

PJYelton

  • Power of Voodoo
  • Jackass In Charge
  • Posts: 1597
  • Karma: +56/-12
    • TheRecursiveFractal
Re: Algorithm help needed
« Reply #3 on: June 21, 2011, 01:31:32 PM »
Bin packing algorithm?

Although to be honest this doesn't feel like one of the more complicated algorithms.  Couldn't it be solved by simply looping through each teacher from (assuming 10 teachers) 1 to 10, then from 10 to 1, then 1 to 10, etc, assigning the highest remaining value?

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #4 on: June 21, 2011, 01:45:16 PM »
Right now I'm doing the following (which is basically what you have just a different perspective):
Get the list of teachers, get the list of students.  Sort the list of students descending based on their score.  90% of the student-teacher pairs will be using this score.  For each student, loop through the teachers and assign the student to the teacher with the lowest total score (after the student-teacher score is taken into account).  Did some simplified tests and that seems to give good results.  I'm now going to pull the "live" (snapshot of live) data and try it there.  The hard part (I imagine) is going to the hard student count limits which may or may not be the same and the fact that there is only a subset of teachers available per student.  Those two means there will be disparity but hopefully it'll still work out.

And yes the bin packing one does seem like the one I'm thinking of.

hans

  • Guitar Addict
  • Jackass In Charge
  • Posts: 3523
  • Karma: +46/-18
Re: Algorithm help needed
« Reply #5 on: June 21, 2011, 02:26:43 PM »
Don't you want to assign the "static" students to teachers before you run through and assign the rest of them?

Nevermind, you said you were going to ignore them. But I don't think it would be that hard to include them in the first run. Just remove them from the remaining set and skip over assignment of other students until all teachers have equal number of kids then continue with your balancing distribution.
This signature intentionally left blank.

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #6 on: June 21, 2011, 02:42:11 PM »
Don't you want to assign the "static" students to teachers before you run through and assign the rest of them?

Nevermind, you said you were going to ignore them. But I don't think it would be that hard to include them in the first run. Just remove them from the remaining set and skip over assignment of other students until all teachers have equal number of kids then continue with your balancing distribution.
In the end the students already assigned won't even be a part of the set I'm looking at and will just be a part of the teacher's beginning score (it'll be pre-computed).  The initial version isn't going to do it just for simplicity reasons and so I can have a picture of what the distribution would be like if we decided not to keep existing assignments.

Can't really do the # of students first as that can easily lead to a state that makes it difficult to balance without shuffling students around.  Had that happen in the very early stages of this project.  Since then I've simplified things down from a very complex problem to a fairly simple problem.

Perspective

  • badfish
  • Jackass In Charge
  • Posts: 4635
  • Karma: +64/-22
    • http://jeff.bagu.org
Re: Algorithm help needed
« Reply #7 on: July 13, 2011, 10:30:23 AM »
What makes this different from traditional bin packing is that the constraint on assigning items (students) to bins (teachers) is the number of items, and not their total weight. Also, the weight of an item depends on the bin it's assigned to.

I'd probably just opt for a greedy assignment algorithm but that's cause I'm lazy.

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #8 on: July 13, 2011, 10:45:22 AM »
This has been a "fun" algorithm to nail down.  I've gotten it to where it numerically looks good.  The problem is now tweaking it so that it is less numerically good and more real world good.  Right now it balances out the total weights nicely but when the assignments are looked at we've got kids assigned to a teacher 20+ miles away while their closes teacher is less than half a mile.  That just doesn't fly.

Perspective

  • badfish
  • Jackass In Charge
  • Posts: 4635
  • Karma: +64/-22
    • http://jeff.bagu.org
Re: Algorithm help needed
« Reply #9 on: July 13, 2011, 01:31:34 PM »
Yet another constraint to add to your cost model. Penalize cost by distance.

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #10 on: July 13, 2011, 02:04:15 PM »
Yet another constraint to add to your cost model. Penalize cost by distance.
Already am.  In fact it quickly becomes the dominate cost.

Perspective

  • badfish
  • Jackass In Charge
  • Posts: 4635
  • Karma: +64/-22
    • http://jeff.bagu.org
Re: Algorithm help needed
« Reply #11 on: July 13, 2011, 02:13:49 PM »
Try a smoothing parameter and get one of the lab monkeys to create a sample of "good" assignments to learn an optimal parameter value.

Cost = alpha * assignment-cost + (1 - alpha) * distance-cost

Mike

  • Jackass In Charge
  • Posts: 11248
  • Karma: +168/-32
  • Ex Asshole - a better and more caring person.
Re: Algorithm help needed
« Reply #12 on: July 13, 2011, 02:30:13 PM »
Try a smoothing parameter and get one of the lab monkeys to create a sample of "good" assignments to learn an optimal parameter value.

Cost = alpha * assignment-cost + (1 - alpha) * distance-cost
Lab monkeys?  Where do you think I work?  And the problem is we don't have a sample of good assignments to choose from and they barely even know what they want.

I'm actually going to be holding off on this until next week's meeting.  I think part of the problem is that the number of students exceed what I expect to have as the number of slots.  So low impact students who are close to a teacher end up getting delayed in their assignment until the higher impact/further students are assigned (to minimize their total costs).  So the low score students end up getting pushed out to further teachers until their score balances.  Unfortunately that works numerically but not in real life context of what we are trying to achieve.  I'm either going to have to limit how far out a student can go before they become an exception that must be dealt with manually or I'm gonna have to look to see how adding that student to a particular teacher affects the teacher's cluster of students and add that as a score.