prob045: Covering Array Problem
Results
In reference [1] an overview of algorithms for this and similar problems in combinatorial
group testing is provided.
In references [3,4] a general constraint-based approach is presented along with values of CAN(3,k,2)
and CAN(4,k,2) (see Table below). The constraint model uses the original Boolean
matrix and the matrix of size ((k choose t) x b) with variables in {0,..,g^t - 1}.
The requirement of having all numbers in {0,..,g^t - 1} in any t rows of the covering
array is satisfied by posting global cardinality constraints on the rows of the second matrix.
The consistency of values of the variables in both matrices is ensured by specialised channelling
constraints. For search to be efficient lexicographic ordering constraints are posted
on the original matrix.
| t |
k |
| 4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 3 |
8*(8) |
10*(12) |
12*(12) |
12*(13) |
12*(13) |
12*(18) |
12*(18) |
12*(18) |
| 4 |
16*(16) |
16*(24) |
21*(28) |
- (38) |
- (42) |
- (50) |
- (50) |
- (-) |
Back to CSPLib home
page.