When Alvin Lim ’02 PhD looks at any problem that involves optimization—whether it’s traffic flow, airline revenues, or grocery prices—he sees something called a Mathema- tical Program with Equilibrium Constraints (MPEC).
MPECs, pioneered by Jong-Shi Pang, former Whiting School of Engineering professor of Mathematical Sciences (now Applied Mathematics and Statistics), offer a model for maximizing the use of resources while addressing the often conflicting goals of planners and users. While studying with Pang, an expert in operations research and MPECs, Lim became interested in the application of MPECs. Pang had three PhD students working in MPEC problems, Lim recalls, “one in finance, another in power distribution, and me in transportation science. The three of us were learning the same math concepts but applying them to completely different fields.”
The wide-ranging implications of MPECs, plus Lim’s understanding of how they can be applied, were recognized when his dissertation, “Transportation Network Design Problems: An MPEC Approach,” received an award from the 2002 Transportation Science Section Dissertation Prize Committee of the Institute for Operations Research and the Management Sciences (INFORMS). Lim’s research involved optimization of the design of transportation networks by explicitly including user equilibrium behavior in the constraints. “What prevents people from solving transportation engineering problems is the difficulty of designing an efficient road network capable of accounting for a natural tendency toward inefficient use,” he explains.
Consider this conundrum: to a traffic planner, the “best” road network is one that is used maximally, and this is how most road networks should be planned. But to a driver, the only system that matters is finding the “best” way from point A to point B. “Best” can mean different things. One person may want to travel quickly; another may prefer a scenic route. The same driver may want to do both at different times, and so on. When a large group of drivers subscribes to the same goal, traffic congestion occurs. This leads to a non-optimal use of the road network due to unbalanced load of the roads. So, drivers’ natural behavior results in inefficient use of the network.
Drivers tend to behave in such a way that only the “best” routes will have traffic flows—a state known as user equilibrium. Ideally, says Lim, planners “should solve their optimization problems based on this ‘selfish’ behavior of drivers.” This is, he says, a “bi-level optimization” problem. “It is difficult to model and solve problems where the conflicting goals of the planners and the users are both taken into account,” he says. “There is no software to solve this.” However, in his dissertation, Lim studied existing ways of forcing more efficient use of the road 2005network, such as setting tolls or adjusting timing of traffic lights. He also proposed possible solutions to resulting MPEC optimization problems by applying the appropriate algorithms.
The power of MPECs are not limited to solving traffic congestion. While he was senior operations research specialist at Delta Technology, a wholly owned subsidiary of Delta Air Lines, Lim applied the MPEC approach to solving the airline passenger optimal overbooking problem and an airline version of the origin-destination demand estimation problem. Like traffic planners, airlines must calculate loads on their airplanes and plan routes accordingly. Once again, consumer behavior bedevils their efforts.
“What airlines do is forecast how many passengers will be there for each flight,” Lim says. “Unfortunately, a consumer does not buy tickets this way; he is interested only in getting from his origin to his destination, which typically requires more than one flight.” It is easy for the airline to collect information at flight level and make predictions based on this data. But it is difficult to predict an individual traveler’s origination and destination. “We are attempting to understand scheduling more in terms of how passengers behave,” Lim explains.
In his current position as optimization consultant at Marketing Analytics in Evanston, Illinois, Lim applies these same optimization concepts to helping clients achieve their marketing goals. For example, he says, “a dominant company, such as Wal-Mart, sets promotional pricing for certain categories of products” and “needs to maximize their sales or profit in anticipation of the pricing the competition might set.” He also helps clients allocate their marketing budget to achieve the best return on investment.
A native of the Philippines, Lim recalls, “I would see these incredible traffic problems in crowded cities and wonder: ‘Why doesn’t it ever help when the government tries to improve traffic? When I came to Hopkins and started applying MPEC to these problems, I began to understand. In certain situations, adding more roads without carefully studying the underlying problem may actually worsen the congestion problems. Now, in my new position, I am shifting gears again, and that is a challenge. But it is all still within the realm of mathematical optimization. That’s the nice thing about mathematical modeling,” he says. “That is what makes it so beautiful.”