Incomplete MaxSAT Approaches for Combinatorial Testing
  We present a Satisfiability (SAT)-based approach for building Mixed Covering
Arrays with Constraints of minimum length, referred to as the Covering Array
Number problem. This problem is central in Combinatorial Testing for the
detection of system failures. In particular, we show how to apply Maximum
Satisfiability (MaxSAT) technology by describing efficient encodings for
different classes of complete and incomplete MaxSAT solvers to compute optimal
and suboptimal solutions, respectively. Similarly, we show how to solve through
MaxSAT technology a closely related problem, the Tuple Number problem, which we
extend to incorporate constraints. For this problem, we additionally provide a
new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we
carry out on the available Mixed Covering Arrays with Constraints benchmarks
and the comparison with state-of-the-art tools confirm the good performance of
our approaches.
