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
MEM, 4/10/96