Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Load-Balancing Strategies for the Parallel Solution of Discrete Optimization Problems

Load-Balancing Strategies for the Parallel Solution of Discrete Optimization Problems

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