Better Living Through Mathematics
by Tony Moore
Imagine a few administrators and their staff shuffling and reshuffling first-year students into and out of classes (on paper) to assign students to their First-Year Seminars of choice. When all 600 or so students have finally landed in their seminars, you might then imagine one administrator turning to another, exhaling deeply and saying, "There's got to be an easier way to do this." And there is, if you can write a handy algorithm to automate the reshuffling—an "elegant solution," as Associate Professor of Mathematics Dick Forrester puts it.
The elegant solution
Forrester's area of scholarship is operations research, a field that uses mathematics to help make complicated decisions, and this assignment seems to have been waiting for him to come along.
"I had been aware of this problem for a while but needed the right student to work on it with me," Forrester says, explaining the algorithm's origins. "Then a couple of years ago, a student, Thanh To ['11], approached me about supervising an honors project with her, and it quickly became clear that she was the perfect student to work on this problem."
The problem Forrester refers to boils down to this: Each student has to pick six possible choices for First-Year Seminars of the 40-plus offered, and then these students must be assigned to one of those six classes so that none of the classes ends up with more than 16 students enrolled.
"The idea of applying mathematics to solve real-life problems really interested me," To, who double majored in economics and mathematics, says of taking the first step toward the elegant solution. "And I had never done anything like his before, so it was very exciting."
Imagining the possible combinations generated by all of the variables arising through this time-consuming process, Forrester says, "I can't even give a ballpark estimate. Let's just say that it is astronomical." And because of this complexity, Forrester saw something especially useful coming out of the project for the college.
"We pitched the idea to the administration—the honors project and the algorithm that would result—and they were very excited about it," he says. Terry Beard in Library & Information Services soon provided Forrester and To the actual seminar-selection data for the three previous years. The two then developed a simple assignment algorithm that would place all students into a seminar of their choice without going over capacity. For all three years, they were able to assign all students to a seminar on their list in less than one second—a task that previously had taken hours.
"So we knew we could automate the process," Forrester says, "but we then wanted to focus on improving the quality of the assignment," which ended up comprising the bulk of their research.
Quality control
"By quality, we mean that the seminars need to be balanced in terms of gender and the number of international students," Forrester explains. "Having such a balance helps to contribute to a diversity of opinions through varying erspectives." As it turned out, quality was emerging as a chief concern: The class assignments their model had generated weren't especially balanced.
Forrester and To refined their model and developed a sophisticated algorithm that not only assigns students to seminars but also maximizes the quality of the resulting solution. It functioned beautifully. "We were able to assign all the students to their seminars with a remarkable balance," Forrester says, noting that they achieved a near-perfect assignment in about two minutes.
While their algorithm worked on previous years' data, Forrester and To were eager to apply it to an incoming class, which they did for the first-year students entering in 2011. "The college has now used the algorithm for the last two years to take all the assignments, and it's worked spectacularly," Forrester says. This success was followed by others, as the paper he and To wrote detailing the project has been accepted for publication by mathematics journal OR Insight, and upon graduation To was awarded the James Fowler Rusling Prize for her overall scholarly achievement.
While the algorithm affects the lives of every incoming student at Dickinson, it may have affected To's life the most. "I was debating whether I should go to graduate school or go to work," she says. "This project helped me realize that I want to pursue the field of operations research further." In fact, To has just completed her first year of graduate studies in operations research at Clemson University, Forrester's own alma mater.
Published August 9, 2012