Runtime-cost trade-off

[Arne DELAET]

Dear Manuel,

I have a question regarding the trade-off between runtime and cost minimization, to which I could not find an answer in the User Guide or in the Google Group.

I have implemented a large neighbourhood search (LNS) heuristic, where I periodically call a mathematical optimization model to solve a planning problem. I want to tune several (6-7) parameters in the algorithm using Irace. However, some parameters are the number of LNS iterations to be performed, the number of calls to the mathematical model for re-optimization, and the neighbourhood size in each LNS iteration. A characteristic of these three parameters is that the higher the value of the parameter (the more LNS iterations and re-optimizations performed and the larger the neighbourhood size), the lower the costs will be. However, there is a time-cost trade-off, as a higher value for each parameter also implies longer runtimes. By performing manual parameter tuning, we have seen that it makes no sense to increase the value of a parameter from a given threshold, as costs will decrease very slightly, and runtime will increase sharply.
My question is as follows: does Irace take such a trade-off into account? If yes, how so? If not, can we do so with some (minor) adjustments?

I am afraid that Irace will always tune the parameters to have high values as they result in the lowest costs, and Irace does not seem to take runtime into account.

Thanks in advance!

Best regards,

Arne

[Manuel López-Ibáñez]

Hi Arne,

You need to define the trade-off (your preferences) yourself. Instead of returning to irace the objective function value of the best solution found by the algorithm, return some kind of weighted sum or Chebycheff scalarization function (https://eprints.whiterose.ac.uk/86090/8/WRRO_86090.pdf) or any of the many methods for scalarizing multiple objectives. You can even use goals and a goal-programming or achievement scalarization function.

It seems likely that your algorithm can report progress over time (best solution value found over time), so an even better alternative would be to return to irace the negative (because irace minimizes) of the hypervolume of the function-value-over-time curve. See https://lopez-ibanez.eu/publications#LopStu2013ejor

For computing the hypervolume of this curve, I typically use an external executable that is called by the target-runner or the target-evaluator (https://github.com/MLopez-Ibanez/irace/tree/master/inst/examples/hypervolume) or the EAF R package (https://mlopez-ibanez.github.io/eaf/reference/hypervolume.html) but with just two "objectives" (solution cost and runtime), it is trivial to calculate the area dominated by the function-value-over-time curve and you could do it yourself in your C++ code.

The paper above also describes how to add preferences via the weighted hypervolume. This is available in the EAF package: https://mlopez-ibanez.github.io/eaf/reference/whv_hype.html

I hope the above is useful!

Manuel.