# Incomplete MaxSAT Approaches for Combinatorial Testing

arXiv: https://arxiv.org/abs/2105.12552 · HTML: https://mlsanity.com/paper/2105.12552/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 51 references that are in the map.
- First posted on arXiv 26 May 2021.

## Builds on (most cited first, 1 of 1)

- [A Commentary on "Breaking Row and Column Symmetries in Matrix Models"](https://mlsanity.com/paper/1910.01423/) (2019)

## Built on by (most cited first, 5 of 5)

- [Generating Streamlining Constraints with Large Language Models](https://mlsanity.com/paper/2408.10268/) (2024)
- [BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit](https://mlsanity.com/paper/2201.05544/) (2022)
- [Incorporating Multi-armed Bandit with Local Search for MaxSAT](https://mlsanity.com/paper/2211.16011/) (2022)
- [A Benchmark Generator for Combinatorial Testing](https://mlsanity.com/paper/2301.08134/) (2022)
- [Enhancing Local Search for MaxSAT with Deep Differentiation Clause Weighting](https://mlsanity.com/paper/2512.05619/) (2025)

## Abstract (arXiv)

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.