Helping computers make faster decisions

Nov 21, 2011 by Christie Taylor

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

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 Ticketmaster.com 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.

Physicists propose solution to constraint satisfaction problems

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

Recommended for you

UT Dallas professor to develop framework to protect computers' cores

Apr 18, 2014

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

Researcher finds hidden efficiencies in computer architecture

Apr 18, 2014

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

More news stories

Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

Airbnb rental site raises \$450 mn

Online lodging listings website Airbnb inked a \$450 million funding deal with investors led by TPG, a source close to the matter said Friday.

Health care site flagged in Heartbleed review

People with accounts on the enrollment website for President Barack Obama's signature health care law are being told to change their passwords following an administration-wide review of the government's vulnerability to the ...

A homemade solar lamp for developing countries

(Phys.org) —The solar lamp developed by the start-up LEDsafari is a more effective, safer, and less expensive form of illumination than the traditional oil lamp currently used by more than one billion people ...

Travelers at Asian airports have asked questions about the March 8 disappearance of Malaysia Airlines Flight 370 while en route from Kuala Lumpur to Beijing. Here are some of them, followed by answers.

NASA's space station Robonaut finally getting legs

Robonaut, the first out-of-this-world humanoid, is finally getting its space legs. For three years, Robonaut has had to manage from the waist up. This new pair of legs means the experimental robot—now stuck ...

Free the seed: OSSI nurtures growing plants without patent barriers

(Phys.org) —Members of the Open Source Seed Initiative this week held a rally and seed giveaway event. The group is concerned over restricting access to seeds through patents. They are stirring up public ...

Filipino tests negative for Middle East virus

A Filipino nurse who tested positive for the Middle East virus has been found free of infection in a subsequent examination after he returned home, Philippine health officials said Saturday.

Egypt archaeologists find ancient writer's tomb

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

Philippines boosts MERS monitoring after UAE nurse scare

The Philippines said Saturday it was stepping up its defences against the deadly MERS virus, with the large numbers of Filipino workers in the Middle East seen as potential carriers.