Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems

This paper studies output-sensitive algorithms for enumeration problems in multiobjective combinatorial optimization (MOCO). We develop two methods for enumerating the extreme points of the Pareto-frontier of MOCO problems. The first method is based on a dual variant of Benson’s algorithm, which has been originally proposed for multiobjective linear optimization problems. We prove that the algorithm runs in output polynomial time for every fixed number of objectives if the weighted-sum scalarization can be solved in polynomial time. Hence, we propose the first algorithm which solves this general problem in output polynomial time. We also propose a new lexicographic version of the dual Benson algorithm that runs in incremental polynomial time in the case that the lexicographic optimization variant can be solved in polynomial time. As a consequence, the extreme points of the Pareto-frontier of the multiobjective spanning tree problem as well as the multiobjective global min-cut problem can be computed in polynomial time for a fixed number of objectives. Our computational experiments show the practicability of our improved algorithm: We present the first computational study for computing the extreme points of the multiobjective version of the assignment problem with five and more objectives. We also empirically investigate the running time behavior of our new lexicographic version compared to the original algorithm.