Riddle you this: You are betting on six soccer games. There are only three outcomes—the home team loses, wins, or ties. What’s the fewest number of tickets you can buy to cover all outcomes and win the most money?
Called the “football pool problem,” this riddle seems simple enough but it’s actually really difficult and people have spent years of computing time trying to solve it to no avail. One of those people is Jim Ostrowski, associate professor and director of graduate studies in the Department of Industrial and Systems Engineering.
Ostrowski was introduced to this problem while in graduate school and it was a game changer for him. The lure of the challenge put him on the path of studying mathematical optimization.
Optimization is the selection of the best element from a set of available options using computational methods. It’s used every day to save time, money, and lives in areas like routing planes, charting delivery trucks, and scheduling surgeries.
One of the known difficulties is eliminating solutions with similar outcomes—known as symmetric solutions—that slow down the process and make problems harder to solve.
“Optimization is finding the best solution possible given the constraints that you have,” explained Ostrowski. “And, that’s hard to do if there are a lot of solutions.”
Ostrowski’s continuing efforts to come up with a solution to having too many solutions have garnered him a DOE Early CAREER award.
In his project, called “Symmetric Convex Sets: Theory, Algorithms, and Application,” Ostrowski notes that the growth in use and improvement of algorithms has allowed computers to take on new roles in areas that require rapid decision making, but some persistent quirks, like symmetric solutions, remain.
“I’m trying to come up with a general algorithm for general problems that addresses this quirk,” he explained. “The tool will help determine what makes problems difficult, and then avoid that difficulty. It will have the power to improve the computational speeds by orders of magnitude.”
In addition to his theoretical research, Ostrowski is developing complex algorithms to be used in real-world situations, particularly as it relates to energy usage.
Every day, around the world, multiple times a day, energy clearinghouses determine the best mix and amount of fuel sources to power our communities. Get it wrong and power can be more costly, unreliable, and harmful to the environment. Ostrowski’s algorithms would optimally schedule power generators while considering pricing, usage, and reliability constraints.
Finding a better solution means fewer fossil fuels and minimizing cost. It also means solving problems faster.”
Ostrowski notes that he anticipates his work, funded by nonprofit organization MISO, to be used in production soon.
Ostrowski is also working on developing the technology for “smart neighborhoods” based in Oak Ridge, Tennessee. These “neighborhoods of the future” use leading-edge microgrid technology to support the community’s energy needs including sources like solar panels, battery storage, and a backup natural gas generator.
Ostrowski is developing optimization algorithms to be used in the software that controls the microgrid and decides when to turn on homes’ systems for use in the most efficient way.
“This work uses forecasted data to develop a market that ensures that the neighborhood’s assets are distributed efficiently. We aim to spread out coast and demand to the different solar or gas systems based on when people use things like their HVAC or water heaters,” he explained.
Common to these projects is the persistent quirk of symmetric solutions. So, when Ostrowski is finished developing his algorithm to help avoid them, his energy-focused research and many other needs, will be a lot easier to tackle.
Ostrowski is also investigating how to harness the power of quantum computing to improve optimization. Currently, it’s not proved very useful, but it can be when blended with traditional computing. Ostrowski plans to look into how to design algorithms that take advantage of the benefits of both types of computing. The result would be much, much faster solutions—and, maybe—finally—a solution to the football pool problem.