Parallel branch, cut, and price for large-scale discrete optimization

Parallel branch, cut, and price for large-scale discrete optimization

0.00 Avg rating0 Votes
Article ID: iaor20051107
Country: Germany
Volume: 98
Issue: 1/3
Start Page Number: 253
End Page Number: 280
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors: , ,
Abstract:

In discrete optimization, most exact solution approaches are based on branch and bound, which is conceptually easy to parallelize in its simplest forms. More sophisticated variants, such as the so-called branch, cut, and price algorithms, are more difficult to parallelize because of the need to share large amounts of knowledge discovered during the search process. In the first part of the paper, we survey the issues involved in parallelizing such algorithms. We then review the implementations of SYMPHONY and COIN/BCP, two existing frameworks for implementing parallel branch, cut, and price. These frameworks have limited scalability, but are effective on small numbers of processors. Finally, we briefly describe our next-generation framework, which improves scalability and further abstracts many of the notions inherent in parallel BCP, making it possible to implement and parallelize more general classes of algorithms.

Reviews

Required fields are marked *. Your email address will not be published.