Helping computers make faster decisions

These algorithms are used in a variety of programs that perform optimization calculations, such as helping Google Maps calculate the shortest route to your destination, or enabling UPS to determine the best way to use its available trucks and staff to complete the day's deliveries.

Previously, though, optimization for a problem that has a high degree of symmetry might be impossible for a computer's capabilities.

Linderoth uses the example of "the football-pool problem," which looks at a system of betting on soccer matches in European countries where participants buy tickets based on the outcome-win, lose or draw-they predict for a series of games. In this problem, the yes/no decision is made for each possible ticket a participant could buy: Should they buy this ticket, or not?

To win the grand prize, a contestant must predict the entire set of matches correctly. But if a participant buys a set of tickets that correctly predicts all but one match, he or she can still win a large sum of money. Currently, computers can calculate the minimum number of tickets a participant might need to buy to ensure they have at least one ticket that is a second-place winner, but only if the number of matches is five or fewer.

For six matches, Linderoth says, the lowest possible number is not yet known, though it previously had been narrowed down to somewhere between 65 and 73. For a computer to make the full calculation, however, would take a massive amount of time.

"The computer will eventually come back with an answer, it just might come back when the universe has already expanded back on itself," Linderoth says.

One reason is that the problem has high amounts of symmetry: The fact that the order in which the matches are listed does not make them different for the purpose of solving the problem. For problems with symmetry, computers can calculate an answer, but not necessarily the best answer.

"It's wasting time searching for answers it's already found," Linderoth says.

Working with Italian colleagues Fabrizio Rossi and Stefano Smriglio, as well as former Ph.D. student Jim Ostrowski, Linderoth and the team developed a methodology that algorithms can use to offset this problem.

The new method breaks solutions into "orbits," or groups of equivalent solutions. Using orbits, an algorithm doesn't have to tackle all symmetrical solutions simultaneously, but can start by just choosing a ticket-any ticket, because initially, they're all equally good. In branching, what you've already chosen will decide what you can choose next.

The orbits change each time a decision is made and must be recalculated. But even with this calculation process, orbits allow optimization algorithms to perform orders of magnitude faster for problems with large amounts of symmetry.

The methodology has already been adopted by commercial optimization software, including the popular product Gurobi, and is already speeding up calculations of integer programs.

"If the problem isn't symmetric it does nothing, but in other types of problems, it's orders of magnitude faster," Linderoth says.

He calls the improvement a "big win" for optimization processes.

As for that six-match lottery ticket? Thanks to orbital branching, we now know the optimal answer is somewhere between 70 and 73.

Provided by University of Wisconsin-Madison