A Classification-based Approach to Managing a Solver Portfolio for CSPs

The utility of using portfolios of solvers for constraint satisfaction problems is well reported. We show that when runtimes are properly clustered, simple classification techniques can be used to predict the class of runtime as, for example, short, medium, long, time-out, etc. Based on runtime classifiers we demonstrate a dispatching approach to solving a set of problem instances in order to minimise the average completion time of each instance. We show that this approach significantly out-performs a well-known CSP solver and performs well against an oracle implementation of a solver portfolio.