The stochastic test collection problem: Models, exact and heuristic solution approaches

Yifat Douek-Pinkovich, Irad Ben-Gal and Tal Raviv

European Journal of Operational Research, 2022, vol. 299, issue 3, 945-959

Abstract: The classic test collection problem (TCP) selects a minimal set of binary tests needed to classify the state of a system correctly. The TCP has applications in various domains, such as the design of monitoring systems in engineering, communication, and healthcare. In this paper, we define the stochastic test collection problem (STCP) that generalizes the TCP. While the TCP assumes that the tests' results can be deterministically mapped into classes, in the STCP, the results are mapped to probability distributions over the classes. Moreover, each test and each type of classification error is associated with some cost. A solution of the STCP is a subset of tests and a mapping of their results to classes. The objective is to minimize the weighted sum of the tests' costs and the expected cost of the classification errors. We present an integer linear programming formulation of the problem and solve it using a commercial solver. To solve larger instances, we apply three metaheuristics for the STCP, namely, Tabu Search (TS), Cross-Entropy (CE), and Binary Gravitational Search Algorithm (BGSA). These methods are tested on publicly available datasets and shown to deliver nearly optimal solutions in a fraction of the time required for the exact solution.

Keywords: Combinatorial optimization; The test collection problem; Integer linear programming; Metaheuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721010997
Full text for ScienceDirect subscribers only

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:eee:ejores:v:299:y:2022:i:3:p:945-959

DOI: 10.1016/j.ejor.2021.12.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().