[Feature Request] hypervolume computation in C/C++

[MLopez-Ibanez]

🚀 Feature Request

Motivation

https://botorch.org/api/utils.html#botorch.utils.multi_objective.hypervolume.Hypervolume

says: TODO: write this in C++ for faster looping.

There is a C (C++ compatible) implementation available here: https://github.com/MLopez-Ibanez/eaf/blob/master/src/mo-tools/hv.c

[sdaulton]

Yeah, that would be nice. Using box decompositions (DominatedPartitioning) to compute hypervolumes seems to work more efficiently than the dimension-sweep algorithm, empirically. Both would likely benefit from C++

[Balandat]

We'd also need this to be auto-differentiable in pytorch though. So the idea was to (maybe) write this using the pytorch C++ frontend as an extension.

[sdaulton]

The current implementation is not differentiable and is simply used for evaluation purposes.

[Balandat]

Oh I see different implementation, my bad.

[MLopez-Ibanez]

Yeah, that would be nice. Using box decompositions (DominatedPartitioning) to compute hypervolumes seems to work more efficiently than the dimension-sweep algorithm, empirically. Both would likely benefit from C++

Maybe. I believe the state-of-the-art is pretty well summarised here: https://dl.acm.org/doi/fullHtml/10.1145/3453474#tab1 And there it recommends the 2D and 3D dimension-sweep algorithms for 2D and 3D. The box-decomposition is only recommended for 5D and 6D.

In any case, I would be surprised if the Python implementation of either algorithm can get anywhere close to the C version of dimension-sweep for 2D and 3D.

It would be nice to have a highly-optimized C/C++ library of fundamental algorithms (not only hypervolume, but dominance filtering, nondominated sorting, other metrics like IGD+ and epsilon, etc) for multi-objective optimization that can be used in R and Python.

[MLopez-Ibanez]

There is a C (C++ compatible) implementation available here: https://github.com/MLopez-Ibanez/eaf/blob/master/src/mo-tools/hv.c

By the way, I'm happy to modify the C code above to make it easier to integrate into BoTorch.

[Balandat]

It would be nice to have a highly-optimized C/C++ library of fundamental algorithms (not only hypervolume, but dominance filtering, nondominated sorting, other metrics like IGD+ and epsilon, etc) for multi-objective optimization that can be used in R and Python.

Indeed, that would be nice.

By the way, I'm happy to modify the C code above to make it easier to integrate into BoTorch.

BoTorch currently doesn't contain any compiled code, which simplifies building and packaging a lot, and so I'd only want to add this to BoTorch if it brings substantial benefits. That said, if this lived in a separate library that is well implemented and maintained I'd be happy to add it as a (potentially optional) dependency. This might more sense especially if the scope for this work is broader and potentially includes more general python and R bindings.