Analysis of the weighted Tchebycheff weight set decomposition for multiobjective discrete optimization problems

Scalarization is a common technique to transform a multiobjective optimization problem into a scalar-valued optimization problem. This article deals with the weighted Tchebycheff scalarization applied to multiobjective discrete optimization problems. This scalarization consists of minimizing the weighted maximum distance of the image of a feasible solution to some desirable reference point. By choosing a suitable weight, any Pareto optimal image can be obtained. In this article, we provide a comprehensive theory of this set of eligible weights. In particular, we analyze the polyhedral and combinatorial structure of the set of all weights yielding the same Pareto optimal solution as well as the decomposition of the weight set as a whole. The structural insights are linked to properties of the set of Pareto optimal solutions, thus providing a profound understanding of the weighted Tchebycheff scalarization method and, as a consequence, also of all methods for multiobjective optimization problems using this scalarization as a building block.