Skip to content

Instantly share code, notes, and snippets.

@jonahgeorge
Forked from Lewuathe/shift.py
Last active January 30, 2016 19:24
Show Gist options
  • Save jonahgeorge/16e7d667b937fd130630 to your computer and use it in GitHub Desktop.
Save jonahgeorge/16e7d667b937fd130630 to your computer and use it in GitHub Desktop.
Optimal assignment of GTAs to Courses via ILP
STUDENTS_PER_TEACHING_ASSISTANT = 30
FTE_PER_SECTION = 0.25
COURSES = [
{ "id": 0, "name": "Computers: Applications And Implications" },
{ "id": 1, "name": "Computer Science Orientation" },
{ "id": 2, "name": "Website Design" },
{ "id": 3, "name": "Introduction To Databases" }
]
SECTIONS = [
{ "id": 0, "course_id": 0, "current_enrollment": 15 },
{ "id": 1, "course_id": 0, "current_enrollment": 30 },
{ "id": 2, "course_id": 1, "current_enrollment": 61 },
{ "id": 3, "course_id": 2, "current_enrollment": 30 },
{ "id": 4, "course_id": 3, "current_enrollment": 35 }
]
STUDENTS = [
{ "id": 0, "name": "Jonah", "fte": 0.25 },
{ "id": 1, "name": "Zane", "fte": 0.25 },
{ "id": 2, "name": "Ty", "fte": 0.25 },
{ "id": 3, "name": "Katie", "fte": 0.50 },
{ "id": 4, "name": "Ben", "fte": 0.25 }
]
STUDENT_PREFERENCES = [
{ "id": 0, "student_id": 0, "section_id": 0, "value": 3 },
{ "id": 1, "student_id": 0, "section_id": 1, "value": 3 },
{ "id": 2, "student_id": 1, "section_id": 1, "value": 3 },
{ "id": 3, "student_id": 1, "section_id": 2, "value": 3 },
{ "id": 4, "student_id": 2, "section_id": 2, "value": 3 },
{ "id": 5, "student_id": 2, "section_id": 3, "value": 3 },
{ "id": 6, "student_id": 3, "section_id": 0, "value": 3 },
{ "id": 7, "student_id": 3, "section_id": 1, "value": 3 },
{ "id": 8, "student_id": 4, "section_id": 2, "value": 3 },
{ "id": 9, "student_id": 4, "section_id": 3, "value": 3 }
]
INSTRUCTORS = [
{ "id": 0, "name": "Eric Walkingshaw" },
{ "id": 1, "name": "Stephen Ramsey" },
{ "id": 2, "name": "Jennifer Parham Mocello" },
{ "id": 3, "name": "Glencora Borradaile" },
{ "id": 4, "name": "Carlos Jensen" }
]
INSTRUCTOR_PREFERENCES = [
{ "id": 0, "instructor_id": 0, "student_id": 0, "section_id": 0, "value": 3 },
{ "id": 1, "instructor_id": 0, "student_id": 0, "section_id": 1, "value": 3 },
{ "id": 2, "instructor_id": 1, "student_id": 1, "section_id": 1, "value": 3 },
{ "id": 3, "instructor_id": 1, "student_id": 1, "section_id": 2, "value": 3 },
{ "id": 4, "instructor_id": 2, "student_id": 2, "section_id": 2, "value": 3 },
{ "id": 5, "instructor_id": 2, "student_id": 2, "section_id": 3, "value": 3 },
{ "id": 6, "instructor_id": 3, "student_id": 3, "section_id": 0, "value": 3 },
{ "id": 7, "instructor_id": 3, "student_id": 3, "section_id": 1, "value": 3 },
{ "id": 8, "instructor_id": 4, "student_id": 4, "section_id": 2, "value": 3 },
{ "id": 9, "instructor_id": 4, "student_id": 4, "section_id": 3, "value": 3 }
]
def find_student_preference_by(student_id, section_id):
preferences = list(filter(lambda s: s["student_id"] == student_id and s["section_id"] == section_id, STUDENT_PREFERENCES))
try:
return preferences[0]["value"]
except:
return 1
def find_course_by(course_id):
course = list(filter(lambda c: c["id"] == course_id, COURSES))
return course[0]
def find_instructor_preference_by(student_id, section_id):
'''
Since Instructor will only be able to set preferences for sections that they "own",
we don't actually need to query INSTRUCTOR_PREFERENCES by `instructor_id`.
Instead, we can just iterate by `student_id` and `section_id` pulling the value, or
the default value of 1
'''
preferences = list(filter(lambda s: s["student_id"] == student_id and s["section_id"] == section_id, INSTRUCTOR_PREFERENCES))
try:
return preferences[0]["value"]
except:
return 1
from constants import *
import pulp
import collections
class GtaAssignmentProblem:
def __init__(self):
'''
Construct the ILP, adds the objective function, and adds constraints
'''
self.problem = pulp.LpProblem('GtaAssignment', pulp.LpMaximize)
self.variables = self._create_variables()
self.problem += self._objective_function()
self._courses_per_student_constraint()
self._students_per_course_constraint()
def _objective_function(self):
'''
Construct objective function from STUDENT_PREFERENCES
'''
obj = None
for student in STUDENTS:
for section in SECTIONS:
student_score = find_student_preference_by(student["id"], section["id"])
instructor_score = find_instructor_preference_by(student["id"], section["id"])
# FIXME: Research more sound way to handle this equation
obj += student_score * self.variables[student["id"]][section["id"]]
obj += instructor_score * self.variables[student["id"]][section["id"]]
print(obj)
exit()
return obj
def _create_variables(self):
'''
Create matrix (students * courses) of binary linear program values
'''
ids = (list(map(lambda s: s["id"], STUDENTS)),
list(map(lambda s: s["id"], SECTIONS)))
return pulp.LpVariable.dicts('VAR', ids, 0, 1, 'Binary')
def _courses_per_student_constraint(self):
'''
This constraint restricting the number of courses per student.
It uses the FTE of the student to determine how many courses
can be assigned to them.
'''
for student in STUDENTS:
c = None
for section in SECTIONS:
c += self.variables[student["id"]][section["id"]]
self.problem += (c <= (student["fte"] // FTE_PER_SECTION))
def _students_per_course_constraint(self):
'''
This constraint restricts the number of TAs per course.
It uses the current_enrollment numbers of the section to determine
the number of TAs to assign.
'''
for section in SECTIONS:
c = None
for student in STUDENTS:
c += self.variables[student["id"]][section["id"]]
self.problem += (c <= (section["current_enrollment"] // STUDENTS_PER_TEACHING_ASSISTANT))
def solve(self):
self.problem.solve()
def results(self):
'''
Print the results of the ILP to STDOUT in pretty-format
'''
for student in STUDENTS:
print(student["name"], "( FTE:", student["fte"], ")")
for section in SECTIONS:
if bool(self.variables[student["id"]][section["id"]].value()):
print("\t", find_course_by(section["course_id"])["name"])
print("")
prob = GtaAssignmentProblem()
prob.solve()
prob.results()
@jonahgeorge
Copy link
Author

New naming for SECTION:

  • segment

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment