Optimal sequential decisions for incomplete identification of group testable items

Abstract

A set of items is called ‘group-testable’ if for any of its subsets it is possible to perform a simultaneous (group) test on the subset with an outcome of "success" or "failure". The "success" outcome indicates that all the tested units are good, and the "failure" outcome indicates that at least one item in the tested subset is defective without knowing which (or how many) are defective. Items of 100% quality cost much more than items of 100q%.quality where q is a positive quantity that is usually greater than 0.9 but strictly less than 1. This is a two-phase decision problem where one must compute the optimal number of cheaper 100q% items to purchase and the optimal group sizes in each stage of the testing process. In this paper first we develop a dynamic programming (DP) model that can be used to find the optimal group sizes in the sequential group-testing process. The optimal solution of the DP is used to find the optimal purchase quantity of the 100q% items. We introduce a heuristic which can reduce the computational complexity of the DP without unduly increasing the expected cost. We discuss several examples of the DP model that finds the optimal group sizes and a non-linear programming model that computes the optimal purchase quantity of the 100q% quality items. Finally, a two-dimensional difference equation is solved to compute the probability of having shortages when the testing is complete.

Keywords:

• group testing
• dynamic programming
• monotone policies