We present techniques for improving the efficiency of ND-trees in the solution of the dynamic nondominance problem, i.e., for building and maintaining a Pareto archive. We propose algorithms for (re)building a tree from a set of nondominated points, either as a space-partitioned ND-tree or by a clustering approach. Numerical experiments confirm that rebuilding the tree at intervals, combined with modified strategies for updating the lower and upper bounds in each node and for computing the distances of points to subtrees in between the rebuilds, can lead to significant speedups over using plain ND-tree-based updates throughout, in particular for higher dimensions.

The repeated filtering of vectors for non-dominance is an important component in many multi-objective programming approaches, like e.g. decomposition approaches, dynamic programming or meta heuristics. Often the set of vectors to be filtered is given as the union A UB or Minkowski sum A + B of Pareto (or stable) sets, i.e. within both sets A and B the vectors are pairwise non-dominated. We propose several algorithms for both problems and compare them to a well-known static divide-and-conquer non-dominance filtering algorithm. Based on numerical experiments, we give recommendations for choosing a suitable method for particular situations, depending on, e.g., the number of objectives or the relative sizes of the sets A and B. Moreover, we consider non-dominance filtering for multi-set sums S = A₁ + ...+ A_s.