TY - GEN
T1 - Adaptation in a CBR-based solver portfolio for the satisfiability problem
AU - Hurley, Barry
AU - O'Sullivan, Barry
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84866689926
U2 - 10.1007/978-3-642-32986-9_13
DO - 10.1007/978-3-642-32986-9_13
M3 - Conference proceeding
AN - SCOPUS:84866689926
SN - 9783642329852
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 152
EP - 166
BT - Case-Based Reasoning Research and Development - 20th International Conference, ICCBR 2012, Proceedings
T2 - 20th International Conference on Case-Based Reasoning, ICCBR 2012
Y2 - 3 September 2012 through 6 September 2012
ER -