Mathematical Contest in Modeling 2007: A Judge’s
Perspective
June 12, 2007
Longtime SIAM MCM judge James Case, after a weekend in California reading and ranking
solution papers submitted for this year's "discrete" problem, discusses the complexities of the
problem and outlines some of the approaches devised by the undergraduate teams.
Between February 8 and February 12, 2007, 949 teams from 12 countries participated in the
23rd annual Mathematical Contest in Modeling. Three hundred fifty-one of the three-person
teams elected to work on the "continuous" problem A, and 598 chose the "discrete" problem B.
A total of 14 papers were judged "outstanding": five for problem A (two from the University of
Washington, and one each from Harvard, MIT, and Duke) and nine for problem B (two from
Duke, and one each from Truman State University, Kirksville, Missouri; Stellenbosch
University, South Africa; Singapore National University; Peking University; the University of
Puget Sound; the National University of Defense Technology, China; and Slippery Rock
University, Slippery Rock, Pennsylvania).
The authors of two of the outstanding papers were named the SIAM winners: the team from
MIT for problem A (see "MIT's 'Dream Team' Wins SIAM Award for MCM 2007" for
highlights of the team's four-year MCM run) and the team from Stellenbosch---Louise Viljoen,
Chris Rohwer, and Andreas Hafver, with faculty adviser Jan van Vuuren---as described here.
With no SIAM Annual Meeting scheduled for this year, the SIAM winners will present their
papers at the 2008 meeting. In the meantime, the UMAP Journal intends to publish five of the
outstanding papers.
The students who worked on the continuous problem were asked to devise a method for
dividing a state into the constitutionally mandated number of congressional districts having the
"simplest" possible geometric shapes, after which they were to apply their method to the state
of New York. The definition of "simplest" was left to the individual teams, who had only to
justify their choice in terms that would be understandable to the public at large. Judges
assigned to the problem reported that contestants reformulated the problem in a wide variety
of ways, and employed an impressive variety of solution techniques.
The discrete problem concerned protocols for boarding and deboarding passenger aircraft.
With the advent of ever-larger planes---the new Airbus model A380 is expected to hold as
many as 800 seats in some configurations---the time spent on the ground (the bulk of which is
devoted to on- and offloading of passengers) can represent a significant fraction of the time an
aircraft and/or crew is in service, as well as a significant drain on airline revenues. Contestants
were asked to devise and compare procedures for boarding and deboarding aircraft of
different sizes: small (85–210 seats), midsize (211–330), and large (450–800).
The simplest way to board an aircraft is simply to open the doors and let the passengers enter
at random. Experience suggests, however, that there are better ways to proceed. Almost all
airlines currently allow first-class passengers and passengers with special needs---including
the elderly, the infirm, and families traveling with small children---to board before others. But in
filling the rest of their seats, individual airlines follow markedly different protocols, with little
consensus as to which ones perform best. The New York Times (November 14, 2006) ran an
article describing airlines' concern with the problem, along with their methods for dealing with it.
To reduce congestion in the aisles, Southwest Airlines has long issued boarding passes
labeled group A, B, or C, on a first-come, first-served basis. Most other airlines assign seats,
often allowing passengers with seats near the back of the plane to enter the cabin as soon as
the preboarding process is complete, followed by passengers with seats amidships, and finally
those seated near the front. Call it the "back to front" (B2F) approach. There is evidence to
suggest---and a number of the MCM teams added to it---that better results might be obtained
by allowing passengers assigned to window seats to be seated before those with middle seats,
who are in turn seated before those in aisle seats. Call that approach WILMA: "window, middle,
aisle." Then there is the "rotating zone" (RZ) approach, which allows a group of passengers
assigned to seats at the rear of the cabin to board first, followed by a group assigned to seats
near the front, who will presumably enter as those in the rear are getting seated. These are
followed by a group to be seated just forward of the first group of passengers, now seated in
the rear, then one just aft of the ones by now seated near the front of the cabin, and so on, until
the groups meet in the middle.
Combining the considerable virtues of B2F and WILMA, the "reverse pyramid" (RP) method
allows people assigned to window seats in the back third of the cabin to enter first, followed by
those assigned either to window seats amidships or middle seats toward the rear. Next come
those with window seats in the front section or middle seats amidships or aisle seats in the
rear, and so on, until only aisle seats near the front of the cabin remain unfilled. The name
refers to the fact that, at any stage of the process, the unfilled seats will form a pyramid
pointing toward the back of the plane.
Many of the MCM teams merely tested---via simulation---the variants of the foregoing
protocols obtained by varying the numbers and sizes of the boarding groups. Others invented
alternative protocols to test against those in current use, or used genetic algorithms to do the
inventing for them. Most observed that enplaning was a more serious problem than deplaning,
and advised that cabin crews refrain from interfering with the latter. It was also widely noted
that baggage is the enemy of boarding efficiency, and advised that carry-on luggage be strictly
limited.
The team from Stellenbosch( @1 o* t1 ~% A. ` University that won the SIAM award for the discrete
problem tested a total of ten boarding protocols---again via simulation---before concluding that
the reverse pyramid method with about nine groups performs as well as any. They
distinguished themselves for their thoroughness in assessing a wide range of possibilities.
Readers can find detailed information about the Mathematical Contest in Modeling, including
complete results for MCM 2007
下面是 MIT 对“梦之队” 取得特等奖历程的描述
MIT’s “Dream Team” Wins SIAM Award for MCM 07
June 12, 2007
Michelle Sipics
If you've followed the Mathematical Contest in Modeling for the past four years, three names
probably sound pretty familiar: Dan Gulotta, Daniel Kane, and Andrew Spann.
The three MIT seniors have participated in the MCM since their freshman year, when they
earned the second-highest ranking ("Meritorious"), along with the Ben Fusaro Award for the
most creative solution. Since then, it's been "Outstanding" all the way, topped off with the
INFORMS Award for the best paper on the discrete problem in 2006 and with a SIAM Award in
this, their final year together.
"The string of success by this team is truly inspiring, and to my knowledge, unprecedented,"
says Martin Bazant, an associate professor of applied mathematics at MIT and the institute's
MCM coach since 2001.
But this team's MCM involvement dates back even further than freshman year. Both Spann
and Gulotta competed in the high school version of the MCM (HiMCM), and when they arrived
at MIT, Spann did some recruiting.
"Spann handpicked his teammates from among his fellow freshmen, [and] came to me with
what would become MIT's Dream Team," Bazant explains. "He was proactive and determined
to compete in the MCM from Day 1 at MIT."
And compete they did, despite their busy schedules. All three team members, on their way to
graduate school, are leaving MIT with double majors: Gulotta and Kane in mathematics and
physics, Spann in mathematics and chemical engineering. Yet somehow they managed to find
time to not only compete in MCM, but to be wildly successful in each contest for the past four
years.
What made that possible, Spann says, is that the contest doesn't especially require training
during what he calls the "off-season." But, he says, "you do need to spend an immense
amount of time during that 96-hour period being focused on your work for the contest, so I'm
glad it only occurs once a year."
This year, those 96 hours ran from February 8 to February 12 (see "Mathematical Contest in
Modeling 2007: A Judge's Perspective"). As always, the contest offered participating teams
the choice of two problems: one continuous and the other discrete. In their first three years,
Bazant's "Dream Team" consistently chose the discrete problem, and in studying this year's
choices, the students' initial instinct was to go for the hat trick in "Outstanding" discrete
problem solving. The discrete problem involved airline boarding, and Spann was already
familiar with some of the research literature on the topic.
Kane, however, had other ideas. The continuous problem was about gerrymandering: Teams
were asked to "develop a model for ‘fairly' and ‘simply' determining congressional districts for a
state." Kane felt that the gerrymandering problem offered the team more options than the
airline boarding problem, and spent the first night of the contest experimenting with ideas for it.
"One of the first things I tried was to minimize the mean square distance of people in the same
district," he says. "After looking at the problem for a while, I reformulated it in terms of moment
of inertia, and figured out how to determine the regions given their centers of mass.
"[That] allowed me to show that the regions would be convex---which I think is what finally
convinced everyone to go with this problem," Kane explains.
Kane's best idea turned out not to be novel. "It was similar to some of the very first ideas that
researchers had proposed when studying the problem in the 1960s," Spann explains---but
then, this isn't the 1960s.
"We had access to faster computing resources than those researchers did, so we were able to
present the results in a new way," Spann says. Gulotta, who handled programming for the
team, found a way to use data from the Census Bureau's database, and the students were
able to compute results for any state they wanted to investigate. With Spann doing most of the
writing and organization, Gulotta doing the programming, and Kane focusing on the
development of the mathematical model and analysis, the three closed their MCM run with a
bang.
"Individually, [these] students are clearly very gifted," Bazant says of the team members.
"However, what impressed me most about the team and their solution papers was their ability
to work closely together with highly complementary and well-orchestrated contributions. I think
the whole was really more than the sum of its parts."
That the students were able to combine their insights and work together in a mathematical
competition is not surprising in light of their individual histories: All three claim longtime interest
in mathematics and its practical applications, and all three have significant experience
participating in--and winning--academic competitions.
Gulotta traces his interest in physics to a book on atoms that he read as a fourth grader; from
that point on, he read as much as possible about nuclear energy and subatomic particles. He
went on to take a physics class as a freshman in high school and, he says, "really enjoyed
being able to use mathematics to predict things about the real world." He took a National
Outstanding award in the HiMCM, and was a gold medalist in the International Physics
Olympiad.
While in high school, Spann too became a regular participant in academic competitions:
MATHCOUNTS, the USA Mathematical Talent Search, the US Mathematical Olympiad, and
the Physics and National Chemistry Olympiads (as well as the HiMCM). He entered MIT with a
strong mathematics background, but decided to enroll in chemical engineering because of his
previous research in chemistry.
"I discovered that chemical engineering had very little to do with chemistry, at least as I had
perceived [it] in high school," he says. "I actually liked this aspect, so I stayed in chemical
engineering and later added mathematics as a double major when it became apparent that I
could get a math major by taking enough math classes for fun."
As for Kane, his goal has been to become a mathematician "ever since I decided that I didn't
really want to be a fireman at about five." Kane, whom Bazant refers to as a "perennial Putnam
fellow," is also a two-time gold medalist in the International Mathematical Olympiad, and he
recently received the 2007 Morgan Prize.
With his "Dream Team" preparing for graduation, Bazant reflects on their myriad achievements
over the past four years, culminating in this year's SIAM Award. With no SIAM Annual Meeting
scheduled this year, Gulotta, Kane, and Spann will be recognized for their achievement at the
2008 Annual Meeting. Each team member will receive $300 and student memberships in
SIAM.
In the meantime, Bazant is hopeful that MIT's MCM success will continue. "This will be a tough
loss for MIT, but we had another Meritorious team this year, and growing interest in the MCM,"
he says. "Hopefully we will keep the streak going."