Skip to content Skip to main navigation Report an accessibility issue

Algorithms May Enhance Computational Efficiency

Imagine a busy airport. Planes from a dozen airlines take off and land hundreds of thousands of times a day, heading to and from hundreds of cities. Passengers scurry from plane to plane catching connecting flights to arrive at their final destination. To ensure that the whole system works reliably and efficiently, complex and large-scale decisions have to be made.

In mathematical language, the decision-making process can be formulated as what computer scientists call an optimization problem—one that looks for the best possible solution out of many alternatives. In the airport setting, this approach will ensure that thousands of planes can take off and land in an orderly fashion and relatively on schedule.

Optimization models that fully capture the essence of industrial-scale problems require computational capacities afforded only by high-performance computing systems. Oleg Shylo, assistant professor of industrial and systems engineering, is hoping to utilize these systems in his JDRD work by designing new algorithms to work in parallel.

“The approach that we’re taking is so-called cooperative solvers, where a group of optimization algorithms work together and, as the word cooperative implies, they communicate with each other to solve problems,” said Shylo.

The use of cooperative solvers comes with its own unique set of constraints, as the communication between these algorithms can quickly overwhelm the system’s bandwidth. Optimization problems frequently have a large number of variables and need to be solved very quickly, something that can’t happen if algorithms are using all the computing power to share updates.

“As in human communication, if you have 10,000 people talking to each other at the same time it’s going to be chaotic and you won’t have time to do any useful work,” said Shylo. “The same applies to algorithms. You need to design communication structures and topologies to alleviate those kinds of issues.”

Shylo will use theoretical models to discover the best communication structures. Through his LDRD partnership with Jack Wells, director of science for the Oak Ridge Leadership Computing Facility at ORNL, Shylo will have the opportunity to test his algorithms on one of the high-performance computing systems, such as Titan, at the national lab. He hopes these tests will confirm his theoretical work and clear the path toward solving real-world optimization problems.