Communications of the ACM
Helping Computers Make Faster Decisions
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. 
, Bethesda, Maryland, USA
No entries found