Planning, placement and more: Optimization makes it easier
Posted August 13, 2007
Cynthia Phillips looks at mundane things like packing a bag or driving across town differently than most people.
To her, they represent questions of optimization – problems that seek to maximize or minimize desired quantities or qualities. That means finding the best solution from among a myriad of possible combinations.
“Everyone makes decisions that could be thought of as optimization problems,” says Phillips, an applied mathematician and distinguished technical staff member at the Department of Energy’s Sandia National Laboratory in New Mexico.
For instance, “People who pack moving vans do a fantastic job with a
very difficult geometric optimization problem,” Phillips says.
“That’s very hard for computers to do.”
Phillips and her fellow researchers are out to make those kinds of jobs easier for computers – and the people who use them. They devise algorithms that let computers solve optimization problems quickly and efficiently.
Those problems are far thornier than finding the best ways to make deliveries or schedule workers.
“People can understand the complexities of dealing with (optimization) on an individual basis, and therefore can appreciate the difficulty of trying to do it for tens of thousands of objects that are all competing for resources,” Phillips says.
The algorithms Phillips and her fellow researchers devise or combine have broad uses, including:
- Determining the best spots to place sensors to detect water contamination.
- Finding the best routes to securely move nuclear materials.
- Choosing the best places to locate guards, cameras and sensors to detect intruders.
- How to place and manage wireless sensors for monitoring environmental conditions or numbers of endangered animals.
Every example is a complicated problem. It may include multiple variables and multiple limits, called constraints, on the solution – factors such as time, location and other conditions that must be satisfied in concert with the quantities or qualities to be maximized or minimized.
