Abstract
Automated configuration procedures play an increasingly prominent role in realising the performance potential inherent in highly parametric solvers for a wide range of computationally challenging problems. However, these configuration procedures have difficulties when dealing with inhomogenous instance sets, where the relative difficulty of problem instances varies between configurations of the given parametric algorithm. In the literature, instance set homogeneity has been assessed using a qualitative, visual criterion based on heat maps. Here, we introduce two quantitative measures of homogeneity and empirically demonstrate these to be consistent with the earlier qualitative criterion. We also show that according to our measures, homogeneity increases when partitioning instance sets by means of clustering based on observed runtimes, and that the performance of a prominent automatic algorithm configurator increases on the resulting, more homogenous subsets.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Hutter, F., Babić, D., Hoos, H., Hu, A.: Boosting verification by automatic tuning of decision procedures. In: Procs. FMCAD 2007, pp. 27–34. IEEE Computer Society Press (2007)
KhudaBukhsh, A., Xu, L., Hoos, H., Leyton-Brown, K.: SATenstein: Automatically building local search sat solvers from components. In: Boutilier, C. (ed.) Procs. IJCAI 2009, pp. 517–524. AAAI Press/The MIT Press (2009)
Tompkins, D.A.D., Balint, A., Hoos, H.H.: Captain Jack: New Variable Selection Heuristics in Local Search for SAT. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 302–316. Springer, Heidelberg (2011)
Hutter, F., Hoos, H.H., Leyton-Brown, K.: Automated Configuration of Mixed Integer Programming Solvers. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 186–202. Springer, Heidelberg (2010)
Vallati, M., Fawcett, C., Gerevini, A., Hoos, H.H., Saetti, A.: Generating fast domain-specic planners by automatically conguring a generic parameterised planner. In: Procs. PAL 2011, pp. 21–27 (2011)
Hoos, H.H.: Programming by optimisation. Communications of the ACM (to appear, 2012)
Ansótegui, C., Sellmann, M., Tierney, K.: A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 142–157. Springer, Heidelberg (2009)
Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Kaufmann, M. (ed.) Procs. GECCO 2009, pp. 11–18. ACM Press (2002)
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, 267–306 (2009)
Hutter, F., Hoos, H.H., Stützle, T.: Automatic algorithm configuration based on local search. In: Procs. AAAI 2007, pp. 1152–1157. AAAI Press (2007)
Hutter, F., Hoos, H.H., Leyton-Brown, K.: Tradeoffs in the Empirical Evaluation of Competing Algorithm Designs. Annals of Mathematics and Artificial Intelligenc (AMAI), Special Issue on Learning and Intelligent Optimization 60(1), 65–89 (2011)
Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC - Instance-Specific Algorithm Configuration. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) Procs. ECAI 2008, pp. 751–756. IOS Press (2010)
Lindawati, Lau, H.C., Lo, D.: Instance-Based Parameter Tuning via Search Trajectory Similarity Clustering. In: Coello, C.A.C. (ed.) LION 5. LNCS, vol. 6683, pp. 131–145. Springer, Heidelberg (2011)
Gomes, C., Selman, B.: Algorithm portfolios. Journal of Artificial Intelligence 126(1-2), 43–62 (2001)
Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: Portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research 32, 565–606 (2008)
Hutter, F., Hamadi, Y., Hoos, H.H., Leyton-Brown, K.: Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 213–228. Springer, Heidelberg (2006)
Xu, L., Hoos, H.H., Leyton-Brown, K.: Hydra: Automatically configuring algorithms for portfolio-based selection. In: Fox, M., Poole, D. (eds.) Procs. AAAI 2010, pp. 210–216. AAAI Press (2010)
Rice, J.: The algorithm selection problem. Advances in Computers 15, 65–118 (1976)
Xu, L., Hoos, H.H., Leyton-Brown, K.: Hierarchical Hardness Models for SAT. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 696–711. Springer, Heidelberg (2007)
Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models: Methodology and a case study on combinatorial auctions. Journal of the ACM 56(4), 1–52 (2009)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M.T., Ziller, S.: A Portfolio Solver for Answer Set Programming: Preliminary Report. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 352–357. Springer, Heidelberg (2011)
Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential Model-Based Optimization for General Algorithm Configuration. In: Coello, C.A.C. (ed.) LION 5. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011)
Smith-Miles, K.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Computing Surveys 41(1), 6:1–6:25 (2008)
Guerri, A., Milano, M.: Learning Techniques for Automatic Algorithm Portfolio Selection. In: de Mántaras, R.L., Saitta, L. (eds.) Procs. ECAI 2004, pp. 475–479. IOS Press (2004)
Kotthoff, L., Gent, I., Miguel, I.: A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems. In: Borrajo, D., Likhachev, M., López, C. (eds.) Procs. SoCS 2011, pp. 84–91. AAAI Press (2011)
Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: Veloso, M. (ed.) Procs. IJCAI 2007, pp. 386–392. AAAI Press/The MIT Press (2007)
MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Cam, L., Neyman, J. (eds.) Procs. Mathematical Statistics and Probability, vol. 1, pp. 281–297. University of California Press (1967)
Bishop, C.: Pattern Recognition and Machine Learning (Information Science and Statistics), 1st edn. 2006. corr. 2nd printing edn. Springer (2007)
Ward, J.: Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association 58(301), 236–244 (1963)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press (2003)
Zarpas, E.: Benchmarking SAT Solvers for Bounded Model Checking. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 340–354. Springer, Heidelberg (2005)
Hamerly, G., Elkan, C.: Learning the k in k-means. In: Procs. NIPS 2003, MIT Press, Cambridge (2003)
Hamadi, Y., Jabbour, S., Sais, L.: ManySAT: a parallel SAT solver. Journal on Satisfiability, Boolean Modeling and Computation 6, 245–262 (2009)
Streeter, M., Golovin, D., Smith, S.: Combining Multiple Heuristics Online. In: Procs. AAAI 2007, pp. 1197–1203. AAAI Press (2007)
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm Selection and Scheduling. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 454–469. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schneider, M., Hoos, H.H. (2012). Quantifying Homogeneity of Instance Sets for Algorithm Configuration. In: Hamadi, Y., Schoenauer, M. (eds) Learning and Intelligent Optimization. LION 2012. Lecture Notes in Computer Science, vol 7219. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34413-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-34413-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34412-1
Online ISBN: 978-3-642-34413-8
eBook Packages: Computer ScienceComputer Science (R0)