optuna
Introduce lazy greedy algorithm to `_solve_hssp`
Motivation
Practically speed-up _solve_hssp() using lazy greedy algorithm.
Description
The current implementation of _solve_hssp() relies on the greedy algorithm for submodular maximization problems with a cardinality constraint. the greedy algorithm guarantees the best approximation ratio of $1-1/e$ (refer to https://doi.org/10.1007/BFb0121195) for monotone cases and obtains practically good solution for non-monotone cases.
To further enhance performance, I propose introducing the lazy greedy algorithm (see https://doi.org/10.1007/BFb0006528) to the hypervolume subset selection problems. This extension allows the algorithm to strategically delay oracle calls until necessary, leveraging the submodular property for practical speed improvements over the naive greedy algorithm. Notably, the number of oracle calls is maintained at most equivalent to the original greedy algorithm.
This straightforward combination of contribution calculation and lazy strategy has been experimentally validated in https://doi.org/10.1109/CEC48606.2020.9185878.
Alternatives (optional)
We need to examine benchmark results to judge whether the lazy strategy really accelerates _solve_hssp(). This is because lazy greedy has the overhead of heap operations and can be slow depending on the input.
Additional context (optional)
No response
Hey would I be able to work on this. Just out of curiosity however, would this deal with backend more?
Also, is there anything I need to know when reproducing the environment other than just following the ReadME?
Thanks
Thank you very much for expressing your interest in contributing to our repository.
To get started, I recommend reviewing CONTRIBUTING.md, which outlines guidelines and instructions for initiating contributions.
Regarding this issue, it involves understanding the algorithm's functionality and comparing benchmark results before and after. We are going to decide whether to use a lazy greedy algorithm based on these comparisons. Consequently, it might seem overwhelming for those who haven't contributed to our repositories before, unless this particular issue aligns well with your preferences.
If you're enthusiastic about contributing, we have several issues tagged with contribution-welcome. These are specifically designed for newcomers, offering a smooth entry into the project. Feel free to choose any of these issues.
Ok cool, I will try and look for a contribution-welcome tag issue. But if nobody takes up this issue after I finish with the welcome issue, then I will give this a shot
Thanks