Transformation-based Feature Computation for Algorithm Portfolios
  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.
