Optimal assignment of GTAs to Courses via ILP

.gitignore

__pycache__

constants.py

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

gta_assignment.py

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()

• Create SECTIONS fixture
• Associate STUDENT_PREFERENCES with SECTIONS
• Associate SECTIONS with COURSES
• Create INSTRUCTORS fixture
• Create INSTRUCTOR_PREFERENCES fixture
• Associate INSTRUCTOR_PREFERENCES with SECTIONS and STUDENTS

New naming for SECTION:

• segment