Annals of Operations Research 90 (1999)

Preface The advent of parallel computation has raised many expectations in many scientific areas, not less so in the fields of continuous and discrete optimization: faster resolution of known problem instances, the possibility to solve large instances of difficult problems, the opportunity to address new problems, etc. Consecutively, a flurry of research activities has been initiated, and parallel computing and optimization now form a significant research field in their own right, characterized, in particular, by the rapid evolution of parallel technologies and computing environments, the ever increasing number of methodological and industrial applications, the development of new methods and the actualization of some old ones due to parallel “thinking”, etc. Parallel computing emerges as one of the most powerful and versatile tools available today to address complex and large-scale problems. Yet, the potential gains of parallel computation do not materialize easily. In fact, parallel computation challenges researchers to rethink their models and algorithms, and imposes a number of specific issues related, in particular, to efficient data structures, communication and information-sharing mechanisms, workload distribution, performance measures, etc. There is now a significant body of scientists in Operations Research and Mathematical Programming actively involved in addressing these issues, and developing sound and efficient PARALLEL OPTIMIZATION models and algorithms in a wide variety of application contexts. An increasing number of conferences, scientific papers and books are dedicated to the subject. The present volume is the first volume of the Annals of Operations Research dedicated to PARALLEL O PTIMIZATION . It follows an international conference organized by PRISM and CRT in 1996. This event has been at the origin of PAREO, the EURO Working Group on Parallel Processing in Operations Research, that together with colleagues from Canada and the USA aims to bring together researchers, students and professionals from around the world interested in parallel computing and its applications, in particular, to operations research and optimization. Turning to the thirteen papers that make up this volume, not surprisingly one notices that the bulk of the volume is dedicated to three of the most active areas of research: branch-and-bound, stochastic programming, and metaheuristics. In all these areas, the solution spaces are enormous, and methods to speed up the search are of prime importance. The last group of papers addresses specific application areas that also display complex mathematical structures and large-scale solution spaces. The first four papers address issues related to parallel implementations of branchand-bound algorithms. Clausen and Perregaard study the two most used search strategies in branch-and-bound enumeration, the best- and deep-first approaches, and conclude the superiority of the latter in a parallel environment. Bixby, Cook, Cox and Lee propose and extensively experiment with a branch-and-cut algorithm for mixedinteger programming formulations. The next paper, by Brüngger, Marzetta, Fukuda and Nievergelt, addresses the important issue of building specialized libraries that © J.C. Baltzer AG, Science Publishers

Preface

allow the combination of powerful methods for many different problems, and to solve them on a host of different platforms. The last paper of the group presents applications of parallel branch-and-bound methods to an important class of formulation: the cluster analysis problem, discussed by Iyer and Aronson. Parallel stochastic programming is the subject of the next group of papers. Vladimirou and Zenios survey the state-of-the-art on parallel algorithms for stochastic programming with emphasis on solving large-scale problem instances. Solving very large linear and nonlinear problem instances is also the focus of the paper by Escudero, de la Fuente, García and Prieto. They use an augmented Lagrangian decomposition method, while Dempster and Thompson parallelize the nested Benders decomposition method. Metaheuristics have significantly emerged as a method of choice to find good solutions to complex formulations. Parallelization strategies aim, here as for other algorithmic approaches, to speed up the search. They also aim to improve the quality of the solutions found and to enhance the robustness of the search relative to the different problem characteristics. Verhoeven and Severens develop efficient parallel local search methods for large instances of Steiner tree problems on graphs. Kohlmorgen, Schmeck and Haase compare various fine-grained parallel genetic algorithms on several combinatorial optimization problems. The last group of papers addresses various applications by using parallel optimization methods. Drozdowski and Kubiak study the scheduling of parallel tasks. Bougeard and Caquineau develop parallel linear and nonlinear optimization methods for robust estimation of statistical parameters used in evaluating large data sets from astronomical experiences. Berner, McKinnon and Millar use parallel branch-andbound, plus a host of other methods, to determine the appropriate number of phases for a class of chemical procedures. Finally, Popp, Pattipati and Bar-Shalom show how parallel computation may significantly enhance the solving of the tracking problem, particularly relevant to the air traffic control problem. To conclude, we would like to thank all those who made possible the first Parallel Optimization Colloquium where this collection of papers originated. We also desire to thank all the authors and express our gratitude to the referees who helped all of us produce this volume. T.G. Crainic C. Roucairol