Parallel Computing in Optimization: (7 Applied Optimization)

During the last three decades, breakthroughs in computer technology have made an impact on optimization. In particular, parallel computing has made it possible to solve larger and computationally more difficult problems. The book covers recent developments in novel programming and algorithmic aspects of parallel computing as well as technical advances in parallel optimization. Each contribution is essentially expository in nature, but of scholarly treatment. In addition, each chapter includes a collection of problems. The first two chapters discuss theoretical models for parallel algorithm design and their complexity. The next chapter gives the perspective of the programmer practicing parallel algorithm development on real world platforms. Solving systems of linear equations efficiently is of importance not only because they arise in many scientific and engineering applications but also because algorithms for solving many optimization problems need to call system solvers and subroutines (chapters four and five). Chapters six to 13 are dedicated to optimization problems and methods. They include parallel algorithms for network problems, parallel branch and bound techniques, parallel heuristics for discrete and continuous problems, decomposition methods, parallel algorithms for variational inequality problems, parallel algorithms for stochastic programming, and neural networks.

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 Stochastic Programming.- 1 Introduction.- 2 Stochastic 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 Stochastic Refinements of Local Search.- 4 Summary of General Principles for Local Search Parallelization.- 5 Exact Methods: Deterministic Approaches.- 6 Exercises.- 13 Deterministic and Stochastic 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.