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 [Formula: see text] lexicographic epsilon-constraint scalarization problems, where [Formula: see text] 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/ .