Python: Problem Set 9

The topic this week is optimization and clustering. This problem is less intensive than last week, but it does demonstrate the trade offs between finding an optimal solution (time intensive) and an adequate solution to an optimization problem.

The point here is to optimize a student’s schedule given two factors: workload and value as defined in the given dictionary. E.g. {‘6.00′: (10, 1)}, the class 6.00 is worth ten times its estimated workload. Naturally, there must be a constraint to our optimization, in this case the student’s desired maximum workload e.g. 12 might return {‘6.00′: (10, 1), ‘6.01’: (5, 4), ‘6.02’: (5, 6)}. With a workload of 11, no additional courses could be added to the schedule without exceeding the maximum.

The initial optimizations went quickly, creating three possible sorting functions: work, value or val/work ratio. The brute force best possible function was more tricky. I first used itertools.permutation method to calculate all possible solutions, in order to then loop through and pick one. This died on the short_subject_list.txt with just 20 courses. My function here works well enough on eight items, but I will have to check the staff solution to see how we are expected to carry out such a calculation on 20 items.

EDIT: OCW has a solution for PS9, but it is for a completely different assignment. But, I realized I need a combination of all possible schedules, not a permutation of each. This makes a sample size of twenty courses manageable.