Newsgroups: comp.parallel
Path: knife!ananth
From: ananth@knife.cs.umn.edu (Ananth)
Subject: Report : Survey of Parallel Discrete Opt. techs..
Sender: news@news2.cis.umn.edu (Usenet News Administration)
Nntp-Posting-Host: knife.cs.umn.edu
Organization: University of Minnesota, Minneapolis, CSci dept.
Date: Mon, 30 Nov 1992 23:43:12 GMT
Lines: 36
Apparently-To: comp-parallel@uunet.uu.net

We just completed a survey of parallel formulations of various
discrete optimization techniques. The report of the same is
available at anonymous ftp site ftp.cs.umn.edu (128.101.230.100),
file:  users/kumar/survey_discrete_opt.ps

The report provides a rather comprehensive tutorial/survey on
parallel backtracking, parallel heuristic search techniques,
speedup anomalies in parallel search, applications such as
integer 0/1 programming, quadratic assignment etc. and
Dynamic Programming.

I am enclosing the abstract herein. I hope this will be of interest
to people and solicit additional references and comments.

Ananth.
AHPCRC / U of Mn.

Parallel Processing of Discrete Optimization Problems: A Survey.

Abstract.

Discrete optimization problems (DOPs) arise in various  applications
such as planning, scheduling, computer  aided design, robotics, game
playing  and  constraint  directed   reasoning.   Often,  a  DOP  is
formulated  in terms of  finding a (minimum cost) solution path in a
graph from  an  initial node to a goal node and solved by graph/tree
search  methods  such  as  branch-and-bound and dynamic programming.
Availability  of parallel computers has created substantial interest
in exploring  the  use  of  parallel processing for solving discrete
optimization problems. This article provides an overview of parallel
algorithms for solving discrete optimization problems.