Multi-objective Problems in Terms of Relational Algebra

Also published as a journal article: Lecture Notes in Computer Science, 2008; 4988:84-98Relational 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 recent 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 singleobjective 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 programs. On the other hand, we address the problem of objective reduction that has recently been shown to be NP-hard. We propose an exact algorithm for this problem based on relational algebra. Our experimental results show that this algorithm drastically outperforms the currently best one.Florian Diedrich, Britta Kehden, and Frank Neuman