Sign In

Communications of the ACM

ACM TechNews

Helping Computers Make Faster Decisions

View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Jeff Linderoth

University of Wisconsin-Madison professor Jeff Linderoth

Credit: University of Wisconsin-Madison

Improvements in the standard algorithm that computers use to solve integer programs enables them to make yes/no decisions faster.

The algorithms are used in programs that perform optimization calculations, but optimization for a problem that has a high degree of symmetry might have been impossible. Computers can calculate an answer for problems with symmetry, but it might not necessarily be the best answer. "It's wasting time searching for answers it's already found," says University of Wisconsin professor Jeff Linderoth.

Working with Italian colleagues Fabrizio Rossi and Stefano Smriglio and former Ph.D. student Jim Ostrowski, Linderoth developed a methodology that algorithms can use to offset the problem. Solutions are broken into orbits, or groups of equivalent solutions, so an algorithm does not have to simultaneously tackle all symmetrical solutions. An algorithm can choose one solution, which will determine what is chosen next. Although the orbits change each time a decision is made and must be recalculated, they allow optimization algorithms to perform orders of magnitude faster for problems with large amounts of symmetry.

From University of Wisconsin-Madison
View Full Article

Abstracts Copyright © 2011 Information Inc. External Link, Bethesda, Maryland, USA 


No entries found