Wednesday, June 19
10:00 AM-12:00 PM
Room 303

MS9
Solving Combinatorial Optimization Problems in Parallel

The search for solutions in a combinatorially large problem space is a major problem in computer science, engineering, and operations research. A general class of difficult and very important combinatorial problems include integer programming problems with linear or nonlinear objective function. Although in the worst case such problems require solution time that grows exponentially as a function of their input size, in practice many instances can be solved in polynomial time by traditional techniques such as divide and conquer and branch and bound methods. Consequently, parallel systems, possibly with hundreds or thousands of processors, give us the opportunity to efficiently solve relatively large instances of hard problems. The speakers in this minisymposium will discuss issues, new results and techniques on the forefront of this important area.

Organizer: Afonso Ferreira
CNRS, France

10:00 Applications with a Parallel Branch and Bound Library
Ricardo Correa, Campus Universitaire, France; and Afonso Ferreira, Organizer
10:30 Parallel Optimization, Load Balancing and Applications
Burkhard Monien and Reinhard Lueling, University of Paderborn, Germany
11:00 New Results on Parallel QAP Solving
Mauricio G.C. Resende, AT&T Bell Laboratories
11:30 Randomization and Approximation Methods for Solving Combinatorial Optimization Problems in Parallel
Jose D.P. Rolim, Universite de Geneve, Switzerland

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index


MEM, 4/10/96