October 1, 2014
By Benjamin Recchie, AB’03
If you have a complex decision to make, one with lots of variables and uncertainties, then Burhaneddin Sandıkçı, associate professor of operations management at the University of Chicago Booth School of Business, wants to help you. He won’t tell you what decisions to make, but he will tell you how to make those decisions by yourself, using the power of stochastic programming models and high-performance computing.
Take an electric utility considering investing in a new generator. How does it know if such a decision is wise? The utility can model usage over the hours of the day, the days of the week, and the month of the year. They can estimate the cost of fuel, the productivity of their generators, and the demand for power in coming years. That’s a lot of factors, but there are uncertainties involved with all those values, and every new variable causes the program to grow exponentially.
Traditionally, Sandıkçı explains, a business like the utility just described would approximate this problem as a linear one and truncate or merge their problem data. “But real life is not only linear,” he warns, and merging or truncating data is equivalent to losing information that is otherwise available. A stochastic programming model could provide a better solution, but it could also contain thousands or even millions of decision variables, making it wildly impractical for most decision-makers to use. (To top it off, he says, if you’re looking for a discrete answer such as “buy a generator” or “don’t buy a generator,” the problem becomes an even more complex subset called a stochastic mixed-integer program.)
So far, stochastic mixed-integer programming models have only been solved for what Sandıkçı describes as “toy” problems, with just a few decision variables. To solve something with millions of variables requires matrices measuring 1 billion by 1 billion. There’s no way a desktop computer could solve such a problem—it couldn’t even store all the data in memory, let alone run Sandıkçı’s program in a reasonable amount of time. When he realized even Chicago Booth’s in-house computing resources would have been overwhelmed by the size of his problems, he turned to the University of Chicago Research Computing Center (RCC).
RCC staff and Sandıkçı developed a way to take advantage of the RCC’s Midway cluster’s multi-core architecture. They parallelized the program, decomposing the enormous matrix into smaller manageable subproblems that a single CPU could handle. The results were then combined to form a solution. Sandıkçı’s program used 1536 CPU cores across 96 compute nodes, and sped up his original program by a whopping 1300 times.
Right now, Sandıkçı’s work is almost entirely theoretical, but he was able to solve some real-world problems posed in the literature. “The scale of the problems we were able to tackle is at least 1000 times larger than what others were able to solve,” he says. “These problems are only a couple years old, but since such a parallel architecture was not used, everything had to be scaled down,” removing the uncertainties to make it simple enough for a desktop computer to do.
Power generation—notoriously tricky to optimize—is just one business problem to which Sandıkçı’s methods could be applied. Once he perfects the theoretical methods, he’ll be able to apply it to other complex decision-making problems, such as commodity markets, transportation and logistics, and the efficient allocation of hospital beds. (In fact, one of Sandıkçı’s students is using RCC resources to work on a small-scale version of the hospital bed problem right now.) The parallelization he and the RCC staff developed scales up almost linearly, too, so even more complex problems might be tackled. “The more cores you give me,” he says with a smile, “the more I will use.”