Helping computers make faster decisions

November 21, 2011 by Christie Taylor, University of Wisconsin-Madison

(PhysOrg.com) -- 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.

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: Website problems for Olympic ticket bidders

Related Stories

Website problems for Olympic ticket bidders

June 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

March 1, 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 Ticketmaster.com and other Web sites.

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

March 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

October 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.

Physicists propose solution to constraint satisfaction problems

October 10, 2011

(PhysOrg.com) -- Maria Ercsey-Ravasz, a postdoctoral associate and Zoltan Toroczkai, professor of physics at the University of Notre Dame, have proposed an alternative approach to solving difficult constraint satisfaction ...

Recommended for you

AI and 5G in focus at top mobile fair

February 24, 2018

Phone makers will seek to entice new buyers with better cameras and bigger screens at the world's biggest mobile fair starting Monday in Spain after a year of flat smartphone sales.

Dropbox files for public stock offering of \$500 mln (Update)

February 23, 2018

Dropbox filed Friday for an initial public offering, seeking to raise an estimated \$500 million for the Silicon Valley cloud computing storage startup.

February 23, 2018

Google said Friday its digital assistant software would be available in more than 30 languages by the end of the years as it steps up its artificial intelligence efforts against Amazon and others.

Stretchable health sensor could improve monitoring of chronic conditions

February 23, 2018

A new type of flexible, wearable sensor could help people with chronic conditions like diabetes avoid the discomfort of regular pin-prick blood tests by monitoring the chemical composition of their sweat instead.

Glitches or not, Nissan starts testing semi-autonomous rides

February 23, 2018

In the future Nissan envisions, driverless cars will pick up children from school and recommend restaurants to tourists in various languages.

Google's digital assistant branches out to Nest camera

February 21, 2018

Google's voice-activated assistant is branching out to Nest's deluxe security camera in an expansion that may amplify the privacy concerns surrounding internet-connected microphones.