The Parallel Epsilon Algorithm for Triobjective Integer Optimization Problems

We propose a new algorithm, the parallel epsilon algorithm (PEA), for enumerating all nondominated images of triobjective integer optimization problems. The algorithm solves at most $2|Y_N|+1$ lexicographic epsilon-constraint scalarization problems, where $Y_N$ is the set of all nondominated images. PEA is easy to implement and easy to parallelize. A novel order on the nondominated set induced by the structure of the parameter set of the lexicographic epsilon-constraint scalarization is utilized to split the computational load into a number of independent parallel tasks. The advantage of the proposed algorithm through parallelization is demonstrated in a computational study. PEA is significantly faster than other state-of-the-art algorithms and achieves an almost linear speedup in the number of threads.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

Funding: The authors gratefully acknowledge the support of the Carl Zeiss Foundation [Grant 2019-01-005] and the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) [GRK 2982, 516090167 “Mathematics of Interdisciplinary Multiobjective Optimization”].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0798) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0798). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.