Abstract
A solver’s runtime and the quality of the solutions it generates are strongly influenced by its parameter settings. Finding good parameter configurations is a formidable challenge, even for fixed problem instance distributions. However, when the instance distribution can change over time, a once effective configuration may no longer provide adequate performance. Realtime algorithm configuration (RAC) offers assistance in finding high-quality configurations for such distributions by automatically adjusting the configurations it recommends based on instances seen so far. Existing RAC methods treat the solver to be configured as a black box, meaning the solver is given a configuration as input, and it outputs either a solution or runtime as an objective function for the configurator. However, analyzing intermediate output from the solver can enable configurators to avoid wasting time on poorly performing configurations. To this end, we propose a gray-box approach that utilizes intermediate output during evaluation and implement it within the RAC method CPPL. We apply cost sensitive machine learning with pairwise comparisons to determine whether ongoing evaluations can be terminated to free resources. We compare our realtime gray-box configurator to a black-box equivalent on several experimental settings and show that our approach reduces the total solving time in several scenarios.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adenso-Díaz, B., Laguna, M.: Fine-tuning of algorithms using fractional experimental designs and local search. Operat. Res. 54, 99–114 (2006)
Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.: Model-based genetic algorithms for algorithm configuration. In: International Joint Conferences on Artificial Intelligence Organization (IJCAI) (2015)
Ansótegui, C., Sellmann, M., Tierney, K.: A gender-based genetic algorithm for the automatic configuration of algorithms. In: Principles and Practice of Constraint Programming - CP 2009, pp. 142–157 (2009). https://doi.org/10.1007/978-3-642-04244-7_14
Astudillo, R., Frazier, P.I.: Thinking inside the box: a tutorial on grey-box Bayesian optimization. In: 2021 Winter Simulation Conference (WSC), pp. 1–15 (2021). https://doi.org/10.1109/WSC52266.2021.9715343
Audemard, G.: Glucose and Syrup in the SAT Race 2015. In: SAT Competition 2015 (2015)
Bahnsen, A.C., Aouada, D., Ottersten, B.: Example-dependent cost-sensitive decision trees. Expert Syst. Appl. 42(19), 6609–6619 (2015). https://doi.org/10.1016/j.eswa.2015.04.042
Biere, A.: CaDiCaL at the SAT Race 2019. In: SAT Race 2019 - Solver and Benchmark Descriptions, p. 2 (2019)
Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 11–18 (2002)
El Mesaoudi-Paul, A., Bengs, V., Hüllermeier, E.: Online Preselection with Context Information under the Plackett-Luce Model (2020)
El Mesaoudi-Paul, A., Weiß, D., Bengs, V., Hüllermeier, E., Tierney, K.: Pool-based realtime algorithm configuration: a preselection bandit approach. In: Kotsireas, I.S., Pardalos, P.M. (eds.) LION 2020. LNCS, vol. 12096, pp. 216–232. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-53552-0_22
Fitzgerald, T., Malitsky, Y., O’Sullivan, B.: ReACTR: realtime algorithm configuration through tournament rankings. In: International Joint Conferences on Artificial Intelligence Organization (IJCAI), pp. 304–310 (2015)
Fitzgerald, T., Malitsky, Y., O’Sullivan, B.J., Tierney, K.: ReACT: real-time algorithm configuration through tournaments. In: Annual Symposium on Combinatorial Search (SoCS) (2014)
Friedrich, T., Krohmer, A., Rothenberger, R., Sutton, A.: Phase Transitions for scale-free SAT formulas. In: Association for the Advancement of Artificial IntelligenceSPONSORSHIP (AAAI), pp. 3893–3899 (2017)
Giráldez-Cru, J., Levy, J.: A modularity-based random SAT instances generator. In: International Joint Conferences on Artificial Intelligence Organization (IJCAI), pp. 1952–1958 (2015)
Guo, S., Sanner, S., Graepel, T., Buntine, W.L.: Score-based Bayesian skill learning. In: European conference on Machine Learning and Knowledge Discovery in Databases (ECMLPKDD), pp. 106–121 (2012). https://doi.org/10.1007/978-3-642-33460-3_12
Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Learning and Intelligent Optimization (LION), p. 507–523 (2011)
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. (JAIR), p. 267–306 (2009)
Hutter, F., et al.: Aclib: a benchmark library for algorithm configuration. In: International Conference on Learning and Intelligent Optimization (LION), pp. 36–40 (2014). https://doi.org/10.1007/978-3-319-09584-4_4
IBM: IBM ILOG CPLEX Optimization Studio: CPLEX User’s Manual (2016). https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.studio.help/pdf/usrcplex.pdf
Li, L., Jamieson, K.G., DeSalvo, G., Rostamizadeh, A., Talwalkar, A.: Efficient hyperparameter optimization and infinitely many armed bandits. CoRR abs/1603.06560 (2016). http://arxiv.org/abs/1603.06560
López-Ibáñez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Operat. Res. Perspect. pp. 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002
Pardalos, P.M., Rasskazova, V., Vrahatis, M.N.: black box optimization, machine learning, and no-free lunch theorems. Springer International Publishing (2021). https://doi.org/10.1007/978-3-030-66515-9
Pushak, Y., Hoos, H.: Golden parameter search: exploiting structure to quickly configure parameters in parallel. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 245–253 (2020). https://doi.org/10.1145/3377930.3390211
Santos, H., Toffolo, T.: Python MIP: Modeling examples (2018–2019). Accessed 23 Jan 2020. https://engineering.purdue.edu/~mark/puthesis/faq/cite-url/
Schede, E., et al.: A survey of methods for automated algorithm configuration (2022)
Speck, D., Biedenkapp, A., Hutter, F., Mattmüller, R., Lindauer, M.: Learning heuristic selection with dynamic algorithm configuration. CoRR abs/2006.08246 (2020). https://arxiv.org/abs/2006.08246
Tsymbal, A.: The problem of concept drift: definitions and related work. Tech. rep., Department of Computer Science, Trinity College, Dublin (2004)
Acknowledgements
The authors are supported in part by the funding program Zentrales Innovationsprogramm Mittelstand (ZIM) (Grant No. ZF4622601LF8) of the German Federal Ministry for Economic Affairs and Climate Action, and the project Maschinelle Intelligenz für die Maschinelle Intelligenz für die Optimierung von Wertschöpfungsnetzwerken (MOVE) (Grant No. 005-2001-0042) of the “it’s OWL” funding of the Ministry of Economics, Innovation, Digitalization and Energy of the German state of North Rhine-Westphalia. The authors would also like to thank the Paderborn Center for Parallel Computation (PC\(^2\)) for the use of the OCuLUS and Noctua clusters.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Weiss, D., Tierney, K. (2022). Realtime Gray-Box Algorithm Configuration. In: Simos, D.E., Rasskazova, V.A., Archetti, F., Kotsireas, I.S., Pardalos, P.M. (eds) Learning and Intelligent Optimization. LION 2022. Lecture Notes in Computer Science, vol 13621. Springer, Cham. https://doi.org/10.1007/978-3-031-24866-5_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-24866-5_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24865-8
Online ISBN: 978-3-031-24866-5
eBook Packages: Computer ScienceComputer Science (R0)