State of the art in parallel search techniques for discrete optimization problems

Ananth Grama, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

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 languageEnglish (US)
Pages (from-to)28-35
Number of pages8
JournalIEEE Transactions on Knowledge and Data Engineering
Volume11
Issue number1
DOIs
StatePublished - 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.

Fingerprint

Dive into the research topics of 'State of the art in parallel search techniques for discrete optimization problems'. Together they form a unique fingerprint.

Cite this