Transformation-based Feature Computation for Algorithm Portfolios
This work addresses the need for accurate features in algorithm portfolios for CSPs, which is incremental as it builds on existing SATzilla features and encodings.
The paper tackled the problem of feature representation for algorithm portfolios in constraint satisfaction problems (CSPs) by computing alternative feature sets on different SAT encodings, showing that these features maintain structural information to differentiate instances and enable effective portfolio-based solving.
Instance-specific algorithm configuration and algorithm portfolios have been shown to offer significant improvements over single algorithm approaches in a variety of application domains. In the SAT and CSP domains algorithm portfolios have consistently dominated the main competitions in these fields for the past five years. For a portfolio approach to be effective there are two crucial conditions that must be met. First, there needs to be a collection of complementary solvers with which to make a portfolio. Second, there must be a collection of problem features that can accurately identify structural differences between instances. This paper focuses on the latter issue: feature representation, because, unlike SAT, not every problem has well-studied features. We employ the well-known SATzilla feature set, but compute alternative sets on different SAT encodings of CSPs. We show that regardless of what encoding is used to convert the instances, adequate structural information is maintained to differentiate between problem instances, and that this can be exploited to make an effective portfolio-based CSP solver.