Multi-objective Problems in Terms of Relational Algebra

Abstract. Relational algebra has been shown to be a powerful tool for solving a wide range of combinatorial optimization problems with small computational and programming effort. The problems considered in re-cent years are single- objective ones where one single objective function has to be optimized. With this paper we start considerations on the use of relational algebra for multi-objective problems. In contrast to single-objective optimization multiple objective functions have to be optimized at the same time usually resulting in a set of different trade-offs with respect to the different functions. On the one hand, we examine how to solve the mentioned problem exactly by using relational algebraic pro-grams. On the other hand, we address the problem of objective reduction that has recently been shown to be NP-hard. We propose an exact al-gorithm for this problem based on relational algebra. Our experimental results show that this algorithm drastically outperforms the currently best one.