Scaling Exact Multi-Objective Combinatorial Optimization by Parallelization

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.