Running an allocation simulation repeatedly breaks after the first run.
Posted
by Az
on Stack Overflow
See other posts from Stack Overflow
or by Az
Published on 2010-05-26T05:22:03Z
Indexed on
2010/05/26
5:31 UTC
Read the original article
Hit count: 434
Background
I have a bunch of students, their desired projects and the supervisors for the respective projects. I'm running a battery of simulations to see which projects the students end up with, which will allow me to get some useful statistics required for feedback. So, this is essentially a Monte-Carlo
simulation where I'm randomising the list of students and then iterating through it, allocating projects until I hit the end of the list. Then the process is repeated again.
Note that, within a single session, after each successful allocation of a project the following take place:
+ the project is set to allocated
and cannot be given to another student
+ the supervisor has a fixed quota
of students he can supervise. This is decremented by 1
+ Once the quota
hits 0, all the projects from that supervisor become blocked
and this has the same effect as a project being allocated
Code
def resetData():
for student in students.itervalues():
student.allocated_project = None
for supervisor in supervisors.itervalues():
supervisor.quota = 0
for project in projects.itervalues():
project.allocated = False
project.blocked = False
The role of resetData()
is to "reset" certain bits of the data. For example, when a project is successfully allocated, project.allocated
for that project is flipped to True
. While that's useful for a single run, for the next run I need to be deallocated.
Above I'm iterating through thee three dictionaries - one each for students, projects and supervisors - where the information is stored.
The next bit is the "Monte-Carlo" simulation for the allocation algorithm.
sesh_id = 1
for trial in range(50):
for id in randomiseStudents(1):
stud_id = id
student = students[id]
if not student.preferences:
# Ignoring the students who've not entered any preferences
for rank in ranks:
temp_proj = random.choice(list(student.preferences[rank]))
if not (temp_proj.allocated or temp_proj.blocked):
alloc_proj = student.allocated_proj_ref = temp_proj.proj_id
alloc_proj_rank = student.allocated_rank = rank
successActions(temp_proj)
temp_alloc = Allocated(sesh_id, stud_id, alloc_proj, alloc_proj_rank)
print temp_alloc # Explained
break
sesh_id += 1
resetData() # Refer to def resetData() above
All randomiseStudents(1)
does is randomise the order of students.
Allocated
is a class defined as such:
class Allocated(object):
def __init__(self, sesh_id, stud_id, alloc_proj, alloc_proj_rank):
self.sesh_id = sesh_id
self.stud_id = stud_id
self.alloc_proj = alloc_proj
self.alloc_proj_rank = alloc_proj_rank
def __repr__(self):
return str(self)
def __str__(self):
return "%s - Student: %s (Project: %s - Rank: %s)" %(self.sesh_id, self.stud_id, self.alloc_proj, self.alloc_proj_rank)
Output and problem
Now if I run this I get an output such as this (truncated):
1 - Student: 7720 (Project: 1100241 - Rank: 1)
1 - Student: 7832 (Project: 1100339 - Rank: 1)
1 - Student: 7743 (Project: 1100359 - Rank: 1)
1 - Student: 7820 (Project: 1100261 - Rank: 2)
1 - Student: 7829 (Project: 1100270 - Rank: 1)
.
.
.
1 - Student: 7822 (Project: 1100280 - Rank: 1)
1 - Student: 7792 (Project: 1100141 - Rank: 7)
2 - Student: 7739 (Project: 1100267 - Rank: 1)
3 - Student: 7806 (Project: 1100272 - Rank: 1)
.
.
.
45 - Student: 7806 (Project: 1100272 - Rank: 1)
46 - Student: 7714 (Project: 1100317 - Rank: 1)
47 - Student: 7930 (Project: 1100343 - Rank: 1)
48 - Student: 7757 (Project: 1100358 - Rank: 1)
49 - Student: 7759 (Project: 1100269 - Rank: 1)
50 - Student: 7778 (Project: 1100301 - Rank: 1)
Basically, it works perfectly for the first run, but on subsequent runs leading upto the nth run, in this case 50, only a single student-project allocation pair is returned.
Thus, the main issue I'm having trouble with is figuring out what is causing this anomalous behaviour especially since the first run works smoothly.
Thanks in advance,
Az
© Stack Overflow or respective owner