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.

The problem of compacting a set of test sequences for sequential circuits is modeled here with the help of a covering matrix, where the test sequences are modeled as columns with variable cost to reflect the cost (number of vectors) of covering selected subsets of circuit faults. From this formulation, reduction rules are extracted, particular to this type of problem which, iteratively applied, result in a significant reduction of the size of the initial compaction problem. A characteristic of the reduction rules is that their application will not compromise the optimum solution of the problem. The remaining reduced problem is then solved by a combination of a heuristic and an exact branch and bound algorithm. Experimental results using the above reduction rules show that the sizes of the given sets of test sequences are often significantly reduced and many times these rules directly produce the absolute minimum of the solution. The final results, compared with others from the literature and also with the absolute minima of the examples, computed separately, support the potential of the proposed approach.