On Objective Conflicts and Objective Reduction in Multiple Criteria Optimization
Dimo Brockhoff, Eckart Zitzler · 2006
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 con-flicting 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 ap-proximation algorithm with optimum approximation ratio and an exact algorithm which works well for small input instances. The paper concludes with experi-mental results for random sets and the multiobjective 0/1-knapsack problem. 1