Abstract
We revisit algorithm selection for declarative programming solvers. We introduce two main ideas to improve cost-sensitive hierarchical clustering: First, to augment the portfolio builder with a self-configuration component. And second, we propose that the algorithm selector assesses the confidence level of its own prediction, so that a more defensive recourse action can be used to overturn the original recommendation.
This work was financially supported in part by TIN2016-76573-C2-2-P.
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
Notes
- 1.
We use the term constraint program to describe all related declarative programming problems, such as mathematical programming, satisfiability, sat modulo theories, quantified Boolean formulae, and of course actual constraint programming.
References
Ansotegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.: Model-based genetic algorithms for algorithm configuration. In: IJCAI, pp. 733–739 (2015)
Bischl, B., et al.: ASlib: a benchmark library for algorithm selection. Artif. Intell. 237, 41–58 (2016)
Cameron, C., Hoos, H.H., Leyton-Brown, K., Hutter, F.: OASC-2017:* zilla submission. In: Open Algorithm Selection Challenge 2017, pp. 15–18 (2017)
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: CP, pp. 454–469 (2011)
Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., Shoham, Y.: A portfolio approach to algorithm selection. In: IJCAI, pp. 1542–1543 (2003)
Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models: methodology and a case study on combinatorial auctions. J. ACM (JACM) 56(4), 22 (2009)
Lindauer, M., van Rijn, J., Kotthoff, L.: Open algorithm selection challenge 2017: setup and scenarios. In: Open Algorithm Selection Challenge 2017, pp. 1–7 (2017)
Lindauer, M., van Rijn, J.N., Kotthoff, L.: The Algorithm Selection Competition Series 2015–17. ArXiv e-prints, May 2018
Lindauer, M., Hutter, F., Hoos, H.H., Schaub, T.: AutoFolio: an automatically configured algorithm selector (extended abstract). In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19–25 August 2017, pp. 5025–5029 (2017)
Liu, T., Amadini, R., Mauro, J.: Sunny with algorithm configuration. In: Open Algorithm Selection Challenge 2017, pp. 12–14 (2017)
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: IJCAI, pp. 608–614 (2013)
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Boosting sequential solver portfolios: knowledge sharing and accuracy prediction. In: 7th International Conference on Learning and Intelligent Optimization, LION 7, Catania, Italy, pp. 153–167 (2013)
O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Irish Conference on Artificial Intelligence and Cognitive Science (2008)
Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for sat. JAIR 32(1), 565–606 (2008)
Xu, L., Hutter, F., Shen, J., Hoos, H., Leyton-Brown, K.: SATzilla2012: improved algorithm selection based on cost-sensitive classification models. In: SAT Competition (2012)
Acknowledgements
We thank the Paderborn Center for Parallel Computation (PC\(^2\)) for the use of their high throughput cluster and Marius Lindauer for his kind help with the OASC benchmarks.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Ansotegui, C., Sellmann, M., Tierney, K. (2018). Self-configuring Cost-Sensitive Hierarchical Clustering with Recourse. In: Hooker, J. (eds) Principles and Practice of Constraint Programming. CP 2018. Lecture Notes in Computer Science(), vol 11008. Springer, Cham. https://doi.org/10.1007/978-3-319-98334-9_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-98334-9_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-98333-2
Online ISBN: 978-3-319-98334-9
eBook Packages: Computer ScienceComputer Science (R0)