Incomplete MaxSAT approaches for combinatorial testing

Thumbnail Image
Ansótegui Gil, Carlos JoséAnsótegui Gil, Carlos José - ORCID ID
Manyà Serres, Felip
Ojeda Contreras, JesúsOjeda Contreras, Jesús - ORCID ID
Salvia Hornos, Josep M.Salvia Hornos, Josep M. - ORCID ID
Torres, Eduard
Other authors
cc-by (c) Ansótegui et al., 2022
Journal Title
Journal ISSN
Volume Title
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.
Related resource
Journal or Serie
Journal of Heuristics, 2022, vol. 28, p. 377-431