# Helping computers make faster decisions

##### November 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.

Explore further: Engineers Take Page Out of Nature's Playbook

## Related Stories

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

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

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

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

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

#### 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

#### Inferring urban travel patterns from cellphone data

August 29, 2016

In making decisions about infrastructure development and resource allocation, city planners rely on models of how people move through their cities, on foot, in cars, and on public transportation. Those models are largely ...

#### How machine learning can help with voice disorders

August 29, 2016

There's no human instinct more basic than speech, and yet, for many people, talking can be taxing. 1 in 14 working-age Americans suffer from voice disorders that are often associated with abnormal vocal behaviors - some of ...

#### Driverless taxi firm eyes operations in 10 cities by 2020

August 29, 2016

A US software firm which chose Singapore for the world's first public trial of driverless taxis hopes to be operating in 10 Asian and US cities by 2020, an executive said Monday.

#### Team introduces 'Braidio' technology, lets mobile devices share power

August 25, 2016

In a paper presented today at the Association for Computing Machinery's special interest group on data communication (SIGCOMM) conference in Florianópolis, Brazil, a team of computer science researchers at the University ...

#### World's first self-driving taxis debut in Singapore

August 25, 2016

The world's first self-driving taxis began picking up passengers in Singapore starting Thursday.

#### Sponge creates steam using ambient sunlight

August 22, 2016

How do you boil water? Eschewing the traditional kettle and flame, MIT engineers have invented a bubble-wrapped, sponge-like device that soaks up natural sunlight and heats water to boiling temperatures, generating steam ...