Column generation applied to linear programs in course registration

The subject of this paper is the application of column generation for solving large linear programs arising in the context of a bidding system for course registration at the Graduate School of Business (GSB), University of Chicago. These LPs are solved in order to assign course schedules to students. The LPs have about 1400 rows and nearly 60 000 columns. The LP software available at the GSB at the time of this study could handle up to 5000 rows and 14 999 columns. Hence, a column generation approach was adopted to solve these LPs. In this study, the basic algorithm is enhanced through a judicious selection of the initial columns and a basis-crashing procedure for the initial restriction of the LP. Computational testing on instances of the LP at the GSB suggests that these enhancements can reduce computational times significantly.