Using Case-based Reasoning in an Algorithm Portfolio for Constraint Solving

It has been shown in areas such as satisfiability testing and integer linear programming that a carefully chosen combination of solvers can outperform the best individual solver for a given set of problems. This selection process is usually performed using a machine learning technique based on feature data extracted from constraint satisfaction problems. In this paper we present CPHYDRA, an algorithm portfolio for constraint satisfaction that uses case-based reasoning to determine how to solve an unseen problem instance by exploiting a case base of problem solving experience. We demonstrate the superiority of our portfolio over each of its constituent solvers using challenging benchmark problem instances from the most recent CSP Solver Competition.