Evaluating the quality of approximations to the non-dominated set

Abstract

: The growing interest in hard multiple objective combinatorial and non-linear problems resulted in a significant number of heuristic methods aiming at generating sets of feasible solutions as approximations to the set of non-dominated solutions. The issue of evaluating these approximations is addressed. Such evaluations are useful when performing experimental comparisons of different multiple objective heuristic algorithms, when defining stopping rules of multiple objective heuristic algorithms, and when adjusting parameters of heuristic algorithms to a given problem. A family of outperformance relations that can be used to compare approximations under very weak assumptions about a decision-maker's preferences is introduced. These outperformance relations define incomplete orders in the set of all approximations. It is shown that in order to compare approximations, which are incomparable according to the outperformance relations, much stronger assumptions about the decision-maker's p...