Distributed Combinatorial Optimization

This paper reports about research projects of the University of Paderborn in the field of distributed combinatorial optimization. We give an introduction into combinatorial optimization and a brief definition of some important applications. As a first exact solution method we describe branch & bound and present the results of our work on its distributed implementation. Results of our distributed implementation of iterative deepening conclude the first part about exact methods. In the second part we give an introduction into simulated annealing as a heuristic method and present results of its parallel implementation. This part is concluded with a brief description of genetic algorithms and some other heuristic methods together with some results of their distributed implementation