Constrained Combinatorial Testing

Concept

Constrained Combinatorial Testing (CCT) is an extension of Combinatorial Testing (CT) that incorporates hard and soft constraints on parameter values, enabling test-suite generation over configurable systems whose valid configurations are restricted by logical dependencies. CCT test suites are formalized as Constrained Mixed-level Covering Arrays (CMCAs), and the optimization problem of finding minimum-size CMCAs has been tackled with greedy, metaheuristic, SAT-based, and Answer Set Programming approaches such as the catnap system.

First seen 7/7/2026

Last seen 7/7/2026

Evidence 4 chunks

Wiki v1

WIKI

Constrained Combinatorial Testing

Definition

Constrained Combinatorial Testing (CCT) is an extension of Combinatorial Testing (CT) that adds explicit constraint handling to the generation of test suites. It is designed for configurable systems in which certain combinations of configuration options are invalid and therefore cannot be exercised. CCT augments strength-t CT with hard constraints (which must always be satisfied) and soft constraints (whose violations should be minimized). As a consequence, CCT can both exclude invalid tuples that cannot be executed and minimize undesirable tuples that are technically executable but problematic in practice ^[1].

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

3 connections

catnap ← implements 100% 2e

catnap is a system for solving CCT problems.

Combinatorial Testing extends → 100% 1e

CCT is defined as an extension of CT with constraint handling.

ASP encoding for strength-2 CCT solving with weak coverage constraints ← implements 100% 1e

The encoding solves CCT with weakened coverage constraints for limiting resources.

LINKED ENTITIES

3 links

catnap IMPLEMENTS Extracted graph relationship

Combinatorial Testing EXTENDS Extracted graph relationship

ASP encoding for strength-2 CCT solving with weak coverage constraints IMPLEMENTS Extracted graph relationship

CITATIONS

6 sources

6 citations — click to expand

[1] Constrained Combinatorial Testing (CCT) is an extension of Combinatorial Testing that adds hard and soft constraint handling for configurable systems. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming

[2] A CMCA(t, k, (v1, ..., vk), C) is an N x k array whose rows satisfy CNF constraint C (domain constraints) and whose t-wise sub-arrays cover every valid t-tuple that satisfies C (coverage constraints); a CMCA is optimal when N is minimal. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming

[3] For the five-option mobile-phone product line, exhaustive testing would need 108 configurations, constraint filtering reduces this to 31, but strength-2 CCT yields an optimal test suite of only 9 test cases covering all 7 valid (Email, Camera) pairs. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming

[4] CCT test-suite optimization is NP-hard in practice; greedy methods are fast but non-optimal, metaheuristics yield smaller suites without guarantees, and SAT-based complete methods are optimal but costly to encode. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming

[5] catnap is an ASP-based CCT solver using clingo that offers a basic encoding for optimal CMCA finding and a weakened encoding that switches coverage constraints from hard to soft to handle resource-bounded instances via lexicographic multi-criteria optimization. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming

[6] The 2019 CCT survey reviewed 129 papers (1987-2018) covering constraint representations, influences, techniques, identification, and maintenance for CT in constrained problem domains. A Survey of Constrained Combinatorial Testing