Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques

Afonso Ferreira, Panos M. Pardalos (auth.), Afonso Ferreira, Panos Pardalos (eds.)354061043X, 9783540610434

Solving combinatorial optimization problems can often lead to runtime growing exponentially as a function of the input size. But important real-world problems, industrial applications, and academic research challenges, may demand exact optimal solutions. In such situations, parallel processing can reduce the runtime from days or months, typical when one workstation is used, to a few minutes or even seconds.
Partners of the CEC-sponsored SCOOP Project (Solving Combinatorial Optimization Problems in Parallel) contributed, on invitation, to this book; much attention was paid to competent coverage of the topic and the style of writing. Readers will include students, scientists, engineers, and professionals interested in the design and implementation of parallel algorithms for solving combinatorial optimization problems.

---

Table of contents :
SCOOP: Solving Combinatorial Optimization problems in parallel….Pages 1-6
Parallel approximation of optimization problems….Pages 7-24
Randomized parallel algorithms….Pages 25-50
Automatic synthesis of parallel algorithms….Pages 51-86
An introduction to parallel dynamic programming….Pages 87-114
Mapping tree-structured combinatorial optimization problems onto parallel computers….Pages 115-144
Towards an abstract parallel branch and bound machine….Pages 145-170
Parallel best-first branch- and-bound in discrete optimization: A framework….Pages 171-200
Building a parallel branch and bound library….Pages 201-231
Parallel algorithms for global optimization problems….Pages 232-247
Parallel heuristic search — Introductions and a new approach….Pages 248-274