Abstract
Discrete optimization problems arise in a variety of domains, such as VLSI design, transportation, scheduling and management, and design optimization. Very often, these problems are solved using state space search techniques. Due to the high computational requirements and inherent parallel nature of search techniques, there has been a great deal of interest in the development of parallel search methods since the dawn of parallel computing. Significant advances have been made in the use of powerful heuristics and parallel processing to solve large-scale discrete optimization problems. Problem instances that were considered computationally intractable only a few years ago are routinely solved currently on server-class symmetric multi-processors and small workstation clusters. Parallel game-playing programs are challenging the best human minds at games like chess. In this paper, we describe the state of the art in parallel algorithms used for solving discrete optimization problems. We address heuristic and nonheuristic techniques for searching graphs as well as trees, and speedup anomalies in parallel search that are caused by the inherent speculative nature of search techniques.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 28-35 |
| Number of pages | 8 |
| Journal | IEEE Transactions on Knowledge and Data Engineering |
| Volume | 11 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1999 |
Bibliographical note
Funding Information:This work is sponsored by U.S. Army Research Office Contract No. DA/DAAG55-98-1-0441, National Science Foundation Grant No. EIA9876014, and the Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory Cooperative Agreement No. DAAH04-95-2-0003/Contract No. DAAH04-95-C-0008. The contents of this paper do not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred.