The world is full of multiple-choice problems in which each choice leads to still more choices in an ever-expanding tree of possibilities. Human beings tackle these problems with intuition, but computers are stuck with trial and error, trying every possible combination until one works.
Cornell computer scientist Carla Gomes has found ways to solve these "combinatorial" problems more quickly. She has received two three-year grants totaling $700,706 from the U.S. Air Force to expand on the research, along with $158,076 for a new high-performance computing facility, which will in itself test new ideas in parallel processing.
The work has applications for such problems as finding the best way to arrange machines in a factory, schedule the distribution of materials or plan aircraft missions. Ultimately, Gomes said, the computing methods she is developing could also be applied to problems in biology, the design of cellular phone networks or the layout of microcircuits.
Combinatorial problems can be described as setting values for a number of variables that must meet certain constraints, Gomes explained. The variables might represent the times and places at which certain events are to take place, and the constraints might be that some of those events must take place before others, or that two of them can't happen in the same place at the same time.
The oldest approach to such problems is brute force: Start at the beginning and try every possible combination. Unfortunately, computer scientists agree, for some problems this could take longer than the age of the universe.
One way to shorten computing time is an approach called randomized backtracking: The computer picks a random starting point and follows all the possible paths from that point. If the answer isn't reached after a specified number of steps, it tries another random starting point.
Backtracking greatly reduces computing time for many problems, but not always. For certain kinds of problems, one run might take seconds, another days, both arriving at the same solution. Gomes, a Cornell research associate in computer science, has discovered that this is because many problems have what mathematicians call "heavy tails." If a lot of random choices are made from a large population, most of them will fall near the average, with just a few being much higher or much lower -- the famous "bell curve."
For combinatorial problems, a graph of the possible combinations versus the time they take to compute is often quite flat in the middle, with long tails, meaning there are almost as many extreme cases as average ones. Gomes and Bart Selman, Cornell professor of computer science, have shown that for some combinatorial problems the tail at the right side of the graph can be very, very long, meaning that there are a vast number of possible starting points leading nowhere. A computer could spend a lot of time in that region, following one dead end after another.
Once you know this, Gomes said, you can introduce "rapid restarting": The computer still performs randomized backtracking, but after a certain number of steps it restarts the entire search. A rapid restart strategy itself always produces a distribution without heavy tails, Gomes said in a paper, "Heavy-Tailed Phenomena in Combinatorial Search," written with Selman and Nuno Crato of New Jersey Institute of Technology, to be presented at the Conference on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics in Washington, D.C., in June.
The research requires a great deal of computing power. In particular, Gomes said, combinatorial problems lend themselves to parallel processing. Gomes plans to experiment with an array of linked desktop computers. The system will consist of 32 top-of-the-line PCs connected via an ultra high-speed network. For the kinds of problems Gomes is considering, she said, such a configuration can match the performance of a supercomputer at only a fraction of the cost.
The Air Force funding is in the form of three separate grants: "Computer-Intensive Methods for Combinatorial Problems" ($395,871), "Hybrid Approaches for Combinatorial Problems" ($304,835) and "A Platform for the Experimental Study of Computer-Intensive Combinatorial Methods in Planning and Scheduling" ($158,076).
| Cornell Chronicle Front Page | | Table of Contents | | Cornell News Service Home Page |