Implement Kung's algorithm to identify non-dominated points

[RasmusML]

Hi,

I am using moocore for several projects (it works great!), and I need a fast and scalable implementation to identify non-dominated points for 4 or more objectives.

As mentioned in the docs, Kung's algorithm is not currently implemented for identifying non-dominated points (and to compute Pareto ranking).

I am therefore opening this issue to track the progress.

For context, I am currently using a Python implementation for Kung's algorithm. However, moving to a C/C++ implementation would be ideal.

Cheers,
Rasmus

[MLopez-Ibanez]

I didn't know about fast-pareto. Thank you! This is precisely why moocore is needed. Good implementations are spread all over the place.

I am all for this! My only limitation is time, so if you wish to contribute it that would be very helpful. Even an initial python implementation would be a step forward.

[MLopez-Ibanez]

I am using moocore for several projects (it works great!), and I need a fast and scalable implementation to identify non-dominated points for 4 or more objectives.

By the way, it would be great to mention your projects here: https://github.com/multi-objective/moocore?tab=readme-ov-file#who-is-using-moocore

[RasmusML]

It appears that seqme is already on the list. Sure, I will create a PR mentioning additional projects, once they are public.

If anyone decides to do a Python implementation, then this may be a good starting point.

Cheers!

[MLopez-Ibanez]

If anyone decides to do a Python implementation, then this may be a good starting point.

I benchmarked seqme.core.rank.is_pareto_front() against moocore.is_nondominated() and the results can be found below. (The version number of seqme is wrong, but the rest should be OK, I can share the benchmarking code if you are interested). seqme is substantially slower. I have not benchmarked non_dominated_rank() but I would expect it to be also much slower than moocore.pareto_rank() even without the implementation of Kung's algorithm. So fast-pareto may be worth looking next, but seqme's implementation does not seem a good starting point.

moocore.is_nondominated() currently does not offer the option to avoid the sorting if the input is already sorted lexicographically, but this is something that could be done relatively easily. And sorting is already quite fast and it could be faster (see #15).

[RasmusML]

Thank you for benchmarking the performance. seqme's implementation is based on fast-pareto's implementation (both in Python), so I would not expect to see any performance difference.

[MLopez-Ibanez]

Then they are not implementing Kung's algorithm correctly. I expect Kung's to be significantly faster than moocore's implementation for 4D and many points, even in Python.

[MLopez-Ibanez]

I have now included fast-pareto in the benchmarks just in case: https://multi-objective.github.io/moocore/python/#identifying-nondominated-points

As you can see, fast-pareto is actually slower than most other Python packages (none of them implementing Kung's algorithm).

For now, moocore is the fastest implementation available in Python so it is not high in my personal list of priorities.
However, there are implementations of Kung's algorithm in C++ and Java, so I think it would be relatively easy to implement it in moocore, if anyone is interested.