Parallel Computing in Optimization

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.