Allocation algorithm help, using Python.

Question

Hi there,

I've been working on this general allocation algorithm for students.

The pseudocode for it (a Python implementation) is:

for a student in a dictionary of students:
    for student preference in a set of preferences (ordered from 1 to 10):
        let temp_project be the first preferred project
        check if temp_project is available
        if so, allocate it to him and make the project unavailable to others
        break

Quite simply this will try to allocate projects by starting from their most preferred. The way it works, out of a set of say 100 projects, you list 10 you would want to do. So the 10th project wouldn't be the "least preferred overall" but rather the least preferred in their chosen set, which isn't so bad.

Obviously if it can't allocate a project, a student just reverts to the base case which is an allocation of None, with a rank of 11.

What I'm doing is calculating the allocation "quality" based on a weighted sum of the ranks. So the lower the numbers (i.e. more highly preferred projects), the better the allocation quality (i.e. more students have highly preferred projects).

That's basically what I've currently got. Simple and it works.

---

Now I'm working on this algorithm that tries to minimise the allocation weight locally (this pseudocode is a bit messy, sorry).

The only reason this will probably work is because my "search space" as it is, isn't particularly large (just a very general, anecdotal observation, mind you). Since the project is only specific to my Department, we have their own limits imposed. So the number of students can't exceed 100 and the number of preferences won't exceed 10.

for student in a dictionary/list/whatever of students:
    where i = 0
    take the (i)st student, (i+1)nd student
    for their ranks: 
        allocate the projects
        and set local_weighting(N) to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank)

    these are the cases:

    if N is 2 (i.e. both ranks are 1):
        then i += 1 and
        and continue above

    if N > 2 (i.e. one or more ranks are greater than 1):
        let temp_N be N:
            pick student with lowest rank 
            and then move him to his next rank
            and pick the other student and reallocate his project

            temp_N is sum of the the ranks

            if temp_N is < N:
                then allocate those projects to the students
                i += 1 
                and move on for the rest of the students

Updated with respect to comments:

---

What I'm trying to do:

• I'm trying to achieve a "lowest weight allocation" between groups of two students at a time (i.e. local)

• The weight allocation is a sum of the ranks as assigned by the students. We want students to get their highest ranked projects overall. Thus if student A has gets a project he ranked 1 and a student B gets a project she ranked 5, then their local allocation weight is 6. If we move student A to his rank 2 project and consequently, student B is moved to her rank 3 project then the weight is now 5. 5 < 6 which is better overall.

• Thus I start with my collection of students and then begin iterating through them

• I start with the first and second student and allocate them their projects

• Then I calculate the weight as described above. Given that the weight is equal to the rankings, if both are ranked 1, the weight 2. This is as good as it gets and we want to move on the second and third students.

• Now, if the weight is greater than 2, indicating that one or more projects is ranked greater than 2, we try to get a better version.

• Thus we take the student with the lowest rank and then move him/her down a single rank (so if he/she was rank 1, this moves him down to rank 2)

• And then we try to re-allocate the other student to another rank.

• Now if the weight is better than the previous weight, then we let that be the new weight and let them have those projects. If it's worse or equal then we just move on to the next duo of students.

• Locally, for students, this thing keeps trying until it's hit a minimum weight and can't do any better.

Hope this explains what I'm trying to do?

---

So, questions:

1. This is sort of a modification of simulated annealing, but any sort of comments on this would be appreciated.

2. How would I keep track of which student is (i) and which student is (i+1)

3. If my overall list of students is 100, then the thing would mess up on (i+1) = 101 since there is none. How can I circumvent that?

4. Any immediate flaws that can be spotted?

Extra info:

My students dictionary is designed as such:

students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences) 
    where preferences is in the form of a dictionary such that
        preferences[rank] = {project_id}

Answer 1

Seems like Assignment Problem might work for you, which can be solved using Hungarian Algorithm (as was noted in your other question: http://stackoverflow.com/questions/2936520/student-project-allocation-algorithms).

Apparently there is a python implementation of the hungarian algorithm: http://pypi.python.org/pypi/hungarian/0.2

I would recommend just using one well known and already implemented algorithm, rather than trying to come up with your own.

If you really want to use your own algorithm and want suggestions on making it work, I suggest you clearly explain what you are trying to do, instead of just providing code.

Good luck, hope that helps.