The generalized test collection problem

Abstract

The test collection problem, also known as the minimum test set problem or the minimum test cover problem, selects a minimal set of binary attributes by which it is possible to determine the state of a system. This problem commonly arises in applications such as medical diagnosis and fault detection in the design of monitoring systems. We generalize this problem by (i) allowing attributes to obtain arbitrary categorical values; (ii) allowing multiple attributes combinations to represent a single state of a system; and (iii) including a different cost for testing each attribute. The objective of the planer is to select a set of tests at a minimum cost that can determine the state of the system. To address this problem, we present an integer programming model and an effective exact solution method that uses the model’s unique structure to reduce its dimension. Using this method, large instances that could not be solved directly by a commercial solver can easily be solved. Our solution method was implemented and demonstrated to be superior to those described in previous studies when applied on two sets of benchmark instances from the literature. One dataset was adapted from the UCI repository and one was based on a realistic and large-scale sensor placement problem in urban water networks.