Planning, placement and more: Optimization makes it easier
(page 2 of 3)
Drifting through space
Phillips and other applied mathematicians call the set of possible solutions “search spaces” – and while they aren’t infinite, search spaces often are enormous.
“People talk about search spaces that contain more potential solutions than the number of atoms in the universe,” Phillips says.
“You have to be very intelligent about how you approach the question, or it’s hopeless,” Phillips says. Testing each solution isn’t practical or feasible. Instead, the algorithms she and her colleagues use exploit the structure of the problem to quickly find the right solution “region.”
Phillips often cites as an example a plan to place sensors in a city to detect some kind of contamination.
“If we were considering 50,000 locations in a city for putting down my sensors and I have 200 sensors,” it would be impossible to test every combination of 200 to find the best, Phillips says.
But with discrete optimization, “I know something about that space of feasible solutions geometrically, algebraically or mathematically that allows me to ignore a lot of points I know aren’t going to be interesting,” Phillips says.
For instance, if the goal is to minimize a targeted value, it’s possible to run simple calculations and get a quick possible value for it – a value of 800, for example.
With that in hand, algorithms can test regions of the solution space to see if a better possible solution exists there. In the example, if the region holds no better solution than a value of 1,000, “Well, I already have something that’s better than that” – that value of 800, Phillips says. “I know I can throw everything out of the region without looking in detail at what’s in there.”
Parallel lives
Even with algorithms that limit the possible solutions, high-performance parallel computers – ones that break tasks up into many pieces so multiple processors can work on them for faster results – still are necessary to solve many optimization problems. Phillips and her researchers are designing algorithms that take advantage of that power.
« Previous 1 | 2 | 3 | Print Next »
