Parallel Computing in Optimization

by A. Migdalas (Editor), Panos M. Pardalos (Editor), Sverre Storïy (Editor)

Overview

During the last three decades, breakthroughs in computer technology have made a tremendous impact on optimization. In particular, parallel computing has made it possible to solve larger and computationally more difficult problems. This volume contains mainly lecture notes from a Nordic Summer School held at the Linkoping Institute of Technology, Sweden in August 1995. In order to make the book more complete, a few authors were invited to contribute chapters that were not part of the course on this first occasion. The purpose of this Nordic course in advanced studies was three-fold. One goal was to introduce the students to the new achievements in a new and very active field, bring them close to world leading researchers, and strengthen their competence in an area with internationally explosive rate of growth. A second goal was to strengthen the bonds between students from different Nordic countries, and to encourage collaboration and joint research ventures over the borders. In this respect, the course built further on the achievements of the "Nordic Network in Mathematical Programming" , which has been running during the last three years with the support of the Nordic Council for Advanced Studies (NorFA). The final goal was to produce literature on the particular subject, which would be available to both the participating students and to the students of the "next generation" .

Product Details

ISBN-13:	9781461334026
Publisher:	Springer US
Publication date:	10/13/2011
Series:	Applied Optimization , #7
Edition description:	1997
Pages:	588
Product dimensions:	6.30(w) x 9.45(h) x 0.05(d)

Table of Contents

1 Models for Parallel Algorithm Design: An Introduction.- 1 Introduction.- 2 Shared memory model: PRAM.- 3 Distributed memory models: DMM.- 4 The coarse grained multicomputer model: CGM.- 5 Summary.- 6 Exercises.- 2 Parallel Algorithms and Complexity.- 1 Introduction.- 2 Models of Parallel Computers.- 3 Limits of Parallelism.- 4 Classification of some Important Graph Problems.- 5 Basic Techniques.- 6 Parallel Algorithms Toolbox.- 7 Approximating the Minimum Degree Spanning Tree Problem.- 8 Exercises.- 3 A Programmer’s View of Parallel Computers.- 1 Introduction.- 2 The Memory Hierarchy.- 3 Communication Network.- 4 Future trends.- 5 Exercises.- 4 Scalable Parallel Algorithms for Sparse Linear Systems.- 1 Introduction.- 2 Parallel Direct Cholesky Factorization.- 3 Multilevel Graph Partitioning.- 4 Exercises.- 5 Object Oriented Mathematical Modelling and Compilation to Parallel Code.- 1 Introduction.- 2 ObjectMath.- 3 Background to Parallel Code Generation.- 4 Definitions.- 5 Towards a Parallelising Compiler.- 6 Equation System Level.- 7 Equation Level.- 8 Clustered Task Level.- 9 Explicit Parallelism.- 10 Summary.- 11 Exercises.- 6 Parallel Algorithms for Network Problems.- 1 Introduction.- 2 Parallel processing paradigms.- 3 The shortest path problem.- 4 Linear problems over bipartite graphs.- 5 Convex problems over singlecommodity networks.- 6 Convex problems over multicommodity networks.- 7 Exercises.- 7 Parallel Branch and Bound — Principles and Personal Experiences.- 1 Introduction.- 2 Sequential B&B.- 3 Parallel B&B.- 4 Personal Experiences with GPP and QAP.- 5 Ideas and Pitfalls for Parallel B&B users.- 6 Exercises.- 8 Parallelized Heuristics for Combinatorial Search.- 1 Heuristics for Combinatorial Search.- 2 Local Search.- 3 Simulated Annealing.- 4 TabuSearch.- 5 Genetic Algorithms.- 6 Greedy Randomized Adaptive Search Procedures.- 7 Conclusions.- 8 Exercises.- 9 Parallel Cost Approximation Algorithms for Differentiable Optimization.- 1 Introduction.- 2 Sequential Cost Approximation Algorithms.- 3 Synchronized Parallel Cost Approximation Algorithms.- 4 Partially Asynchronous Parallel Cost Approximation Algorithms.- 5 Concluding Remarks.- 6 Exercises.- 10 Parallel Computation of Variational Inequalities and Projected Dynamical Systems with Applications.- 1 Introduction.- 2 The Variational Inequality Problem.- 3 Projected Dynamical Systems.- 4 Variational Inequality Applications.- 5 Projected Dynamical Systems Applications.- 6 Summary and Conclusions.- 7 Exercises.- 11 Parallel Algorithms for Large-Scale Shastic Programming.- 1 Introduction.- 2 Shastic Programs with Recourse.- 3 Algorithmic Approaches.- 4 Algorithmic Comparisons.- 5 Conclusions.- 6 Exercises.- 12 Parallel Continuous Non-Convex Optimization.- 1 Introduction.- 2 Local Search Heuristics.- 3 Deterministic and Shastic Refinements of Local Search.- 4 Summary of General Principles for Local Search Parallelization.- 5 Exact Methods: Deterministic Approaches.- 6 Exercises.- 13 Deterministic and Shastic Logarithmic Barrier Function Methods for Neural Network Training.- 1 Introduction.- 2 Newton-type and Logarithmic Barrier Methods.- 3 Application to Neural Network Training.- 4 Ill-Conditioning.- 5 Computational Results.- 6 Conclusions and Future Research.- 7 Exercises.