Optimal assignment of students to classes at Tokyo Institute of Technology

This is a report on a case study concerning the optimal assignment of 1,200 freshmen to 14 classes. Each student is entitled to choose three classes and to allocate 100 points to these classes according to his or her degree of preference. ‘Optimal’ assignment is defined here as the one which maximizes the total scores subject to the condition that (i)each student must be assigned to one of the three classes specified by him. (ii)the number of students assigned to each class does not exceed its capacity. The standard mathematical formulation leads to a transportation type linear programming problem. The authors solved this problem by primal-dual algorithm, which takes only one minute on workstation. The quality of its solution outperformed all schemes tried in the past. In particular, the authors found that a satisfactory assignment can be obtained if the total capacity is slightly (ca. 5%) more than the number of students. Also, we incorporated (a)the best method to increase the capacity if there is no feasible assignment, (b)the way to prevent the existence of a class with less than 50% of its capacity, by applying parametric linear programming techniques. [In Japanese.]