Quad-Trees and Linear Lists for Identifying Nondominated Criterion Vectors

In this paper we address the problem of identifying all nondominated criterion vectors in large, finite sets of criterion vectors. Two methods, quad-trees and linear lists, are studied in detail. In discussing the methods, a complete algorithmic description of the quad-tree approach, which builds upon the description given by Habenicht (W. Habenicht, ENUQUAD, an interactive DSS-tool for discrete vector optimization problems, M. Cerny, D. Glückaufova, D. Loula, eds. Multicriteria Decision Making: Methods–Algorithms–Applications, Institute of Economics, Prague, pp. 66–81, 1992.), is specified and computational results are reported. The results show that the quad-tree approach is faster than the linear list approach on problems with large sets of criterion vectors that have more than 2, but fewer than 8, objectives. Also, in general, the larger the proportion of vectors that are nondominated in the set of criterion vectors, the more effective the quad-tree approach.