Abstract
The satisfiability problem was amongst the very first problems proven to be NP-Complete. It arises in many real world domains such as hardware verification, planning, scheduling, configuration and telecommunications. Recently, there has been growing interest in using portfolios of solvers for this problem. In this paper we present a case-based reasoning approach to SAT solving. A key challenge is the adaptation phase, which we focus on in some depth. We present a variety of adaptation approaches, some heuristic, and one that computes an optimal Kemeny ranking over solvers in our portfolio. Our evaluation over three large case bases of problem instances from artificial, hand-crafted and industrial domains, shows the power of a CBR approach, and the importance of the adaptation schemes used.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Biere, A., Heule, M.J.H., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press (February 2009)
Gomes, C.P., Selman, B.: Algorithm Portfolios. Artificial Intelligence 126(1-2), 43–62 (2001)
O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using Case-based Reasoning in an Algorithm Portfolio for Constraint Solving. In: Proceedings of AICS (2008)
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: Portfolio-based Algorithm Selection for SAT. Journal of Artificial Intelligence Research, 565–606 (June 2008)
Pulina, L., Tacchella, A.: A Multi-engine Solver for Quantified Boolean Formulas. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 574–589. Springer, Heidelberg (2007)
Davis, M., Logemann, G., Loveland, D.: A Machine Program for Theorem Proving. Communications of the ACM 5(7), 394–397 (1962)
Fürnkranz, J., Hüllermeier, E.: Pairwise Preference Learning and Ranking. In: Lavrač, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) ECML 2003. LNCS (LNAI), vol. 2837, pp. 145–156. Springer, Heidelberg (2003)
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank Aggregation Methods for the Web. In: Proceedings of the 10th International Conference on World Wide Web, WWW 2001, pp. 613–622. ACM, New York (2001)
Brinker, K., Fürnkranz, J., Hüllermeier, E.: A Unified Model for Multilabel Classification and Ranking. In: Proceedings of the 2006 European Conference on Artificial Intelligence, ECAI 2006, pp. 489–493. IOS Press (2006)
Brinker, K., Hüllermeier, E.: Case-based Multilabel Ranking. In: Proceedings of the 20th International Joint Conference on Artificial intelligence, IJCAI 2007, pp. 702–707. Morgan Kaufmann Publishers Inc., San Francisco (2007)
Brinker, K., Hüllermeier, E.: Case-Based Label Ranking. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 566–573. Springer, Heidelberg (2006)
Gärtner, T., Vembu, S.: Label Ranking Algorithms: A Survey. In: Johannes Fürnkranz, E.H. (ed.) Preference Learning. Springer (2010)
Pacuit, E.: Voting Methods. In: Zalta, E.N. (ed.) The Stanford Encyclopedia of Philosophy, Winter 2011 edn. (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
Hurley, B., O’Sullivan, B. (2012). Adaptation in a CBR-Based Solver Portfolio for the Satisfiability Problem. In: Agudo, B.D., Watson, I. (eds) Case-Based Reasoning Research and Development. ICCBR 2012. Lecture Notes in Computer Science(), vol 7466. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32986-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-32986-9_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32985-2
Online ISBN: 978-3-642-32986-9
eBook Packages: Computer ScienceComputer Science (R0)