Helping computers make faster decisions

Nov 21, 2011 by Christie Taylor

( -- Industrial and systems engineering professor Jeff Linderoth is working on a way to help computers make yes/no decisions faster by enhancing the standard algorithm computers use to solve a class of problems called integer programs.

These algorithms are used in a variety of programs that perform optimization calculations, such as helping 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 .

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.

Explore further: Dartmouth contests showcase computer-generated creativity

Related Stories

Website problems for Olympic ticket bidders

Jun 24, 2011

(AP) -- Thousands of people across Britain rose at dawn and hunched over their computer keyboards in the second round of bidding for tickets for the 2012 London Olympics.

4 charged with hacking into concert ticket sites

Mar 01, 2010

(AP) -- Federal prosecutors in New Jersey say four California men made more than $25 million reselling tickets to concerts and sporting events they acquired by hacking into and other Web sites.

The best time to buy tickets to a sold-out game

Mar 21, 2011

Trying to buy a ticket to a sold-out game? To get the cheapest price you have a decision to make: when to buy. During a visit to a sold-out basketball game at Duke University, "Science Nation" put the question to some die-hard ...

Online games as social meeting places

Oct 12, 2010

boundary crossing in online games, researchers Jonas Linderoth and Camilla Olsson at the University of Gothenburg analyse the culture of online games and the boundary-crossing community associated with the activity. The report ...

Engineers Take Page Out of Nature's Playbook

May 11, 2006

Designing complex systems such as nuclear reactors for space applications is a daunting task, but Oak Ridge National Laboratory researchers have made it less so by borrowing from nature.

Recommended for you

Researchers build first working memcomputer prototype

12 hours ago

(Tech Xplore)—A combined team of researchers from the University of California and Politecnico di Torino in Italy has built, for the first time, a working memory-crunching computer (memcomputer) prototype. ...

EU open source software project receives green light

Jul 01, 2015

An open source software project involving the University of Southampton to extend the capacity of computational mathematics and interactive computing environments has received over seven million euros in EU funding.

Can computers be creative?

Jul 01, 2015

The EU-funded 'What-if Machine' (WHIM) project not only generates fictional storylines but also judges their potential usefulness and appeal. It represents a major advance in the field of computational creativity.

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.