Scaling Exact Multi-Objective Combinatorial Optimization by Parallelization

TitleScaling Exact Multi-Objective Combinatorial Optimization by Parallelization
Publication TypeConference Paper
Year of Publication2014
AuthorsGuo, J., E. Zulkoski, R. Olaechea, D. Rayside, K. Czarnecki, S. Apel, and J. M. Atlee
Conference Name29th IEEE/ACM International Conference on Automated Software Engineering (ASE)
Date Publishedto appear
Conference LocationVästerås, Sweden

Multi-Objective Combinatorial Optimization (MOCO) is fundamental to the development and optimization of software systems. We propose five novel parallel algorithms for solving MOCO problems exactly and efficiently. Our algorithms rely on off-the-shelf solvers to search for exact Pareto-optimal solutions, and they parallelize the search via collaborative communication, divide-and-conquer, or both. We demonstrate the feasibility and performance of our algorithms by experiments on three case studies of software-system designs. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scales well up to 64 cores. Furthermore, we analyze the performance bottlenecks and potential opportunities of our parallel algorithms, which facilitates further research on exact, parallel MOCO.

Refereed DesignationRefereed
ase2014epoal.pdf489.27 KB
ase2014_PPT.pdf1.16 MB