RT Journal Article
T1 Capping methods for the automatic configuration of optimization algorithms
A1 De Souza, Marcelo
A1 Ritt, Marcus
A1 López Ibáñez Infante, Manuel
K1 Algoritmos
AB Automatic configuration techniques are widely and successfully used to find good parameter settings for optimization algorithms. Configuration is costly, because it is necessary to evaluate many configurations on different instances. For decision problems, when the objective is to minimize the running time of the algorithm, many configurators implement capping methods to discard poor configurations early. Such methods are not directly applicable to optimization problems, when the objective is to optimize the cost of the best solution found, given a predefined running time limit. We propose new capping methods for the automatic configuration of optimization algorithms. They use the previous executions to determine a performance envelope, which is used to evaluate new executions and cap those that do not satisfy the envelope conditions. We integrate the capping methods into the irace configurator and evaluate them on different optimization scenarios. Our results show that the proposed methods can save from about 5% to 78% of the configuration effort, while finding configurations of the same quality. Based on the computational analysis, we identify two conservative and two aggressive methods, that save an average of about 20% and 45% of the configuration effort, respectively. We also provide evidence that capping can help to better use the available budget in scenarios with a configuration time limit.
PB Elsevier
YR 2022
FD 2022-03
LK https://hdl.handle.net/10630/24001
UL https://hdl.handle.net/10630/24001
LA eng
NO de Souza, Marcelo ; Ritt, Marcus ; Lopez Ibañez Infante, Manuel. Capping methods for the automatic configuration of optimization algorithms.Computers & Operations Research Volume 139, March 2022, 105615. https://doi.org/10.1016/j.cor.2021.105615
NO This research has been supported by Coordenação de Aperfeiçoa-mento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code001. M. de Souza acknowledges the support of the Santa Catarina State University, Brasil. M. Ritt acknowledges the support of CNPq, Brasil (grant 437859/2018-5) and Google Research Latin America (grant25111). M. López-Ibáñez is a ‘‘Beatriz Galindo’’ Senior Distinguished Researcher (BEAGAL 18/00053) funded by the Spanish Ministry of Science and Innovation (MICINN). This research is partially funded by TAILOR ICT-48 Network (No 952215) funded by EU Horizon 2020research and innovation programme. Funding for open access charge: Universidad de Málaga / CBUA
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 3 mar 2026