| Abstract: |
A common approach in multiobjective optimization is to perform the decision making process after the search process: first, a search heuristic approximates the set of Pareto-optimal
solutions, and then the decision maker chooses an appropriate trade-off solution from the resulting approximation set. Both processes are strongly affected by the number of optimization criteria.
The more objectives are involved the more complex is the optimization problem and the choice for the decision maker. In this context, the question arises whether all objectives are actually
necessary and whether some of the objectives may be omitted; this question in turn is closely linked to the fundamental issue of conflicting and non-conflicting optimization criteria. Besides a
general definition of conflicts between objective sets, we here introduce the problem of computing a minimum subset of objectives without losing information (MOSS) and show that this is an
NP-hard problem. Furthermore, we present for MOSS both an approximation algorithm with optimum approximation ratio and an exact algorithm which works well for small input instances. The paper
concludes with experimental results for random sets and the multiobjective 0/1-knapsack problem. |
