Efficient static compaction of test sequence sets through the application of set covering techniques

The test sequence compaction problem is modelled here, as a set covering problem. This formulation enables the straightforward application of set covering methods for compaction. Because of the complexity inherent in the first model, a second more efficient, formulation is proposed where the test sequences are modelled as matrix columns with variable costs (number of vectors). Further, matrix reduction rules appropriate to the new formulation, which do not affect the optimality of the solution, are introduced. Finally, the reduced problem is minimized with a branch & bound algorithm. Experiments on a large number of test sets show significant reductions to the original problem by simply using the presented reduction rules. Experimental results comparing our method with others form the literature and also with the absolute minima of the examples, computed separately with the MINCOV algorithm, support the potential of the proposed approach.