Parallel Strategies Selection
  We consider the problem of selecting the best variable-value strategy for
solving a given problem in constraint programming. We show that the recent
Embarrassingly Parallel Search method (EPS) can be used for this purpose. EPS
proposes to solve a problem by decomposing it in a lot of subproblems and to
give them on-demand to workers which run in parallel. Our method uses a part of
these subproblems as a simple sample as defined in statistics for comparing
some strategies in order to select the most promising one that will be used for
solving the remaining subproblems. For each subproblem of the sample, the
parallelism helps us to control the running time of the strategies because it
gives us the possibility to introduce timeouts by stopping a strategy when it
requires more than twice the time of the best one. Thus, we can deal with the
great disparity in solving times for the strategies. The selections we made are
based on the Wilcoxon signed rank tests because no assumption has to be made on
the distribution of the solving times and because these tests can deal with the
censored data that we obtain after introducing timeouts. The experiments we
performed on a set of classical benchmarks for satisfaction and optimization
problems show that our method obtain good performance by selecting almost all
the time the best variable-value strategy and by almost never choosing a
variable-value strategy which is dramatically slower than the best one. Our
method also outperforms the portfolio approach consisting in running some
strategies in parallel and is competitive with the multi armed bandit
framework.
