In this talk the dynamic load balancing of highly irregular parallel combinatorical optimization problems is addressed. The load balancing algorithms presented in this talk have been investigated for a number of applications on parallel computing systems collecting up to 1024 processors. The methods guarantee that the parallel combinatorical optimization algorithm achieves nearly linear speedup, even if the parallel computation takes only very short time.

Within the talk, the load-balancing method is presented to solve Vertex Cover problems, Traveling Salesman problems and very large instances of the Quadratic Assignment Problem. A analytical justification of the load-balancing method is given. Using these results it is possible to encapsulate the know-how of these methods in programming frames for the solution of combinatorial optimization problems using branch & bound methods.

An encapsulation of the load-balancing method is presented in form of the Daisy library allowing the easy parallelization of sequential combinatorial optimization problem by solving the load balancing problem in a way which is efficient and easy to handle.

This is joint work with T. Decker, B. Monien and S. Tschoeke.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing