  In Software Product Lines (SPLs) it may be difficult or even impossible to
test all the products of the family because of the large number of valid
feature combinations that may exist. Thus, we want to find a minimal subset of
the product family that allows us to test all these possible combinations
(pairwise). Furthermore, when testing a single product is a great effort, it is
desirable to first test products composed of a set of priority features. This
problem is called Prioritized Pairwise Test Data Generation Problem.
  State-of-the-art algorithms based on Integer Linear Programming for this
problema are faster enough for small and medium instances. However, there
exists some real instances that are too large to be computed with these
algorithms in a reasonable time because of the exponential growth of the number
of candidate solutions. Also, these heuristics not always lead us to the best
solutions. In this work we propose a new approach based on a hybrid
metaheuristic algorithm called Construct, Merge, Solve & Adapt. We compare this
matheuristic with four algorithms: a Hybrid algorithm based on Integer Linear
Programming ((HILP), a Hybrid algorithm based on Integer Nonlinear Programming
(HINLP), the Parallel Prioritized Genetic Solver (PPGS), and a greedy algorithm
called prioritized-ICPL. The analysis reveals that CMSA results in
statistically significantly better quality solutions in most instances and for
most levels of weighted coverage, although it requires more execution time.
