ReACTR: realtime algorithm configuration through tournament rankings
Tadhg Fitzgerald, Yuri Malitsky, Barry O’Sullivan · 2015
It is now readily accepted that automated algorithm configuration is a necessity for ensuring optimized performance of solvers on a particular problem do-main. Even the best developers who have carefully designed their solver are not always able to manu-ally find the best parameter settings for it. Yet, the opportunity for improving performance has been repeatedly demonstrated by configuration tools like ParamILS, SMAC, and GGA. However, all these techniques currently assume a static environment, where demonstrative instances are procured before-hand, potentially unlimited time is provided to ad-equately search the parameter space, and the solver would never need to be retrained. This is not always the case in practice. The ReACT system, proposed in 2014, demonstrated that a solver could be con-figured during runtime as new instances arrive in a steady stream. This paper further develops that approach and shows how a ranking scheme, like TrueSkill, can further improve the configurator’s performance, making it able to quickly find good parameterizations without adding any overhead on the time needed to solve any new instance, and then continuously improve as new instances are evalu-ated. The enhancements to ReACT that we present enable us to even outperform existing static config-urators like SMAC in a non-dynamic setting. 1