Scaling Exact Multi-Objective Combinatorial Optimization by

Multi-Objective Combinatorial Optimization (MOCO) is fun-damental to the development and optimization of software systems. We propose five novel parallel algorithms for solv-ing 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 demon-strate the feasibility and performance of our algorithms by experiments on three case studies of software-system de-signs. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scale well up to 64 cores. Furthermore, we analyze the performance bottlenecks and opportunities of our par-allel algorithms, which facilitates further research on exact, parallel MOCO