The generalized test collection problem

Yifat Douek-Pinkovich (), Irad Ben-Gal () and Tal Raviv ()
Additional contact information
Yifat Douek-Pinkovich: Tel-Aviv University
Irad Ben-Gal: Tel-Aviv University
Tal Raviv: Tel-Aviv University

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2021, vol. 29, issue 2, No 6, 372-386

Abstract: 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.

Keywords: Test collection problem; Sensor selection; Sensor placement; Water networks; Integer linear programming; Constraint reduction; 90C10; 90C27; 90C90; 90B25 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-020-00554-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:29:y:2021:i:2:d:10.1007_s11750-020-00554-1

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-020-00554-1

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().