DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME TWENTY TWO
TITLE: Workshop on Parallel Processing of Discrete Optimization Problems
EDITORS: Panos M. Pardalos, Mauricio G.C. Resende, K.G. Ramakrishnan
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.



PREFACE


Discrete optimization problems (dop's) arise in various applications, such as airline crew scheduling, corporate planning, computer-aided design and manufacturing, communications network design, machine vision, database query design, cellular telephone frequency assignment, and constraint directed reasoning. Often, a dop is formulated in terms of finding a (least 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.

Formally, a dop can be stated as follows: Given a finite discrete set X and a function f(x) defined on the elements of X, find an optimal element x*, such that, f(x*) = min{f(x) | x &epsilon X }. In certain problems, the aim is to find any member of the set S &subset X of all optimal solutions. These problems can also be easily stated in the above format by making f(x) = 0 for all x &epsilon S , and f(x) = 1 for x &epsilon X - S. In most problems of practical interest, the set X is quite large. Consequently, exhaustive enumeration of the elements of X to determine x* is not feasible. Often, elements of X can be viewed as paths in graphs/trees, the cost function can be defined in terms of the cost of the arcs, and the dop can be formulated in terms of finding a (least cost) solution path in the graph from an initial node to a goal node. Branch and bound and dynamic programming methods use the structure of these graphs to solve dop's without searching X exhaustively.

Given that many classes of dop are NP-hard, one may argue that there is no point in applying parallel processing to these problems, as the worst-case run time can never be reduced to a polynomial unless we have an exponential number of processors. However, the average time complexity of heuristic search algorithms for many problems is polynomial. Also, there are some heuristic search algorithms which find suboptimal solutions in polynomial time (e.g., for certain problems, approximate branch-and-bound algorithms are known to run in polynomial time). In these cases, parallel processing can significantly increase the size of solvable problems. Some applications using search algorithms (e.g. robot motion planning, task scheduling) require real time solutions. For these applications, parallel processing is perhaps the only way to obtain acceptable performance. For some problems, optimal solutions are highly desirable, and cab be obtained for moderate sized instances in a reasonable amount of time using parallel search techniques (e.g. vlsi floor-plan optimization).

Parallel computers having thousands of processing elements are now commercially available. The cost of these machines is similar to that of large mainframes, but they offer significantly more raw computing power. Due to advances in vlsi technology and economies of scale, the cose of these machines is expected to go down drastically over the next decade. It may soon be possible to construct computers comprising thousands to millions of processing elements at costs ranging from those of high-end workstations to large mainframes. This technology has created substantial interest in exploring the use of parallel processing for search based applications.

In the context of the 1993-1994 DIMACS special year on parallel computing, a two-day workshop entitled "Parallel Processing of Discrete Optimization Problems" was held on April 28-29. The workshop featured about twenty invited speakers from Europe and North America. This volume contains a collection of refereed papers from the workshop. The papers cover a wide spectrum of algorithms and applications in parallel processing of discrete optimization and related problems.

One of the key successes of the workshop was that collaboration started among the European group of researchers working on the scoop project (Solving Combinatorial Optimization Problems in Parallel) and researchers from U.S. In addition, many participants stayed at DIMACS after the workshop working on joint projects.

The workshop was sponsored by DIMACS with funds from National Science Foundation and The New Jersey Commission on Science and Technology. We would like to take this opportunity to thank the sponsors, the DIMACS staff, the participants, the authors, the referees, and the American Mathematical Society, for making the workshop successful and the publication of this volume possible.

Panos M. Pardalos, Mauricio G.C. Resende, and K.G. Ramakrishnan
December 1994


TABLE OF CONTENTS




Foreword								  xi

Preface									xiii

Proving Correctness for Balancing Networks
    Costas Busch and Marios Mavronicolas				   1

A Note on Parallel Randomized Algorithms for Searching Porblems
    Andrea Clemnti, Jose Rolim and Ludek Kucera				  33

Modeling Parallel Branch-and-Bound for Asynchronoous Implementations	
    Ricardo Correa and Afonso Ferreira					  45

A Data Parallel Space Dilation Algorithm for the Concentrator 
  Location Problem
    Olof Damberg and Athanasios Migdalas				  57

A Multistage Approach for Scheduling Task Graphs on Parallel
  Machines
    Apostolos Gerasoulis, Jia Jiao and Tao Yang				  81

Parallel Algorithms for Satisfiability (SAT) Problem
    Jun Gu								 105

Experiences with a Parallel Formulation of an Interior Point Algorithm
    George Karypis, Anshul Gupta and Vipin Kumar			 163

Experiences with a Synchronous Parallel Branch and Bound Algorithm
    Per S. Laursen							 181

New Anticipatory Load Balancing Strategies for Parallel A* Algorithms
    Nihar R. Mahapatra and Shantanu Dutt				 197

A Parallel Algorithm for Computing all Homomorphisms of Deterministic
  Finite Automata
    Boleslaw Mikolajczak						 233

Query Optimization and Processing in Parallel Databases
    T.M. Niccum, J. Srivastava, B. Himatsingka and J. Li		 259


Scheduling Acyclic Task Graphs on Distributed Memory Parallel 
  Architectures
    Santos Pande and Kleanthis Psarris					 289

Sclability of Massively Parallel Depth-First Search
    Alexander Reinefeld							 305

On Irregular Data Structures and Asynchronous Parallel Brand and 
  Bound Algorithms
    Catherine Roucairol							 323

Parallel Algorithms for the Assignment Problem - An Experimental
  Evaluation of Three Distributed Algorithms
    Christian Schutt and Jens Clausen					 337

Serial & Parallel Algorithms for QSP Problems
    J. MacGregor Smith and Jui Xu					 353


Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.