Generator sets for the Minkowski sum problem

This paper develops a new theoretical framework for generator sets in the context of Minkowski Sum Problems (MSPs) arising in multi-objective optimization. In MSPs, the nondominated set of the global problem equals the nondominated set of the Minkowski sum of several local nondominated sets. We introduce the concept of generator sets: subsets of local nondominated vectors that are sufficient to construct the global nondominated set. We present novel theoretical results that characterize conditions for vectors to belong to a generator set or to be redundant. Moreover, we develop algorithms for finding generator sets and identifying redundant local vectors. Finally, we conduct extensive numerical experiments to test the impact of varying characteristics of the instances on the resulting global nondominated set and the number of redundant vectors.