[Feature Request] Merging two sets of non-dominated points

[light-weaver]

Sometimes we want to merge two (or more) sets of non-dominated solutions, i.e., every solution in a set is non-dominated compared to the other solutions in the same set, but may be dominated, or dominate, solutions in other sets. As an example, we may want to keep an updated archive of non-dominated solutions while running an MOEA. Simply merging the set and then running moocore.is_nondominated can involve a large number of unnecessary comparisons.

I am not too familiar with C, so here's an example Python/numba implementation from DESDEO: non_dominated_merge

[MLopez-Ibanez]

For sure it can be done faster, because if point b in set B dominates a point a in set A, then point a does not need to be checked again because it cannot dominated anything in B. And viceversa. That still gives you O(nkm) in the worst case (everything is nondominated), which is significantly worse that you can get if you merge everything in one set, check for dominance and then separate the two masks.

def non_dominated_merge(set1: np.ndarray, set2: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
    mask = moocore.is_nondominated(np.vstack((set1, set2)), keep_weakly=True) # Or if duplicates should be considered dominated
    set1_mask , set2_mask = np.split(mask, [len(set1)])
    return set1_mask, set2_mask

The above code should be already faster than the current code in DESDEO even with numba for 2D and 3D. It may be even faster for >=4D already and it would be definitely faster when moocore.is_nondominated() implements the best-known algorithm for checking dominance. See https://multi-objective.github.io/moocore/python/reference/generated/moocore.is_nondominated.html for details.

[MLopez-Ibanez]

From a quick benchmarking, the 2D and 3D cases are faster in moocore despite the unnecessary dominance checks. For >=4D, moocore.is_nondominated() is not fast enough to compensate and the current implementation in DESDEO is faster than the naive function above.

Nevertheless, this is something we want to have in moocore as part of the achiving features. Perhaps we should start with a simple unbounded archive that implement s the nondominated merge efficiently.