An efficient dynamic optimization method for sequential identification of group-testable items

Jiejian FENG, Liming LIU, Mahmut PARLAR

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

5 Citations (Scopus)

Abstract

Group testing with variable group sizes for incomplete identification has been proposed in the literature but remains an open problem because the available solution approaches cannot handle even relatively small problems. This article proposes a general two-stage model that uses stochastic dynamic programming at stage 2 for the optimal group sizes and non-linear programming at stage 1 for the optimal number of group-testable units. By identifying tight bounds on the optimal group size for each step at stage 2 and the optimal initial purchase quantity of the group-testable units at stage 1, an efficient solution approach is developed that dramatically reduces both the number of functional evaluations and the intermediate results/data that need to be stored and retrieved. With this approach, large-scale practical problems can be solved exactly within very reasonable computation time. This makes the practical implementation of the dynamic group-testing scheme possible in manufacturing and health care settings.
Original languageEnglish
Pages (from-to)69-83
JournalIISE Transactions
Volume43
Issue number2
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Testing
Nonlinear programming
Health care
Dynamic programming

Cite this

@article{74d6d031120a46949185d9e54abd4b80,
title = "An efficient dynamic optimization method for sequential identification of group-testable items",
abstract = "Group testing with variable group sizes for incomplete identification has been proposed in the literature but remains an open problem because the available solution approaches cannot handle even relatively small problems. This article proposes a general two-stage model that uses stochastic dynamic programming at stage 2 for the optimal group sizes and non-linear programming at stage 1 for the optimal number of group-testable units. By identifying tight bounds on the optimal group size for each step at stage 2 and the optimal initial purchase quantity of the group-testable units at stage 1, an efficient solution approach is developed that dramatically reduces both the number of functional evaluations and the intermediate results/data that need to be stored and retrieved. With this approach, large-scale practical problems can be solved exactly within very reasonable computation time. This makes the practical implementation of the dynamic group-testing scheme possible in manufacturing and health care settings.",
author = "Jiejian FENG and Liming LIU and Mahmut PARLAR",
year = "2010",
doi = "10.1080/0740817X.2010.504684",
language = "English",
volume = "43",
pages = "69--83",
journal = "IISE Transactions",
issn = "2472-5854",
publisher = "Taylor and Francis Ltd.",
number = "2",

}

An efficient dynamic optimization method for sequential identification of group-testable items. / FENG, Jiejian; LIU, Liming; PARLAR, Mahmut .

In: IISE Transactions, Vol. 43, No. 2, 2010, p. 69-83.

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

TY - JOUR

T1 - An efficient dynamic optimization method for sequential identification of group-testable items

AU - FENG, Jiejian

AU - LIU, Liming

AU - PARLAR, Mahmut

PY - 2010

Y1 - 2010

N2 - Group testing with variable group sizes for incomplete identification has been proposed in the literature but remains an open problem because the available solution approaches cannot handle even relatively small problems. This article proposes a general two-stage model that uses stochastic dynamic programming at stage 2 for the optimal group sizes and non-linear programming at stage 1 for the optimal number of group-testable units. By identifying tight bounds on the optimal group size for each step at stage 2 and the optimal initial purchase quantity of the group-testable units at stage 1, an efficient solution approach is developed that dramatically reduces both the number of functional evaluations and the intermediate results/data that need to be stored and retrieved. With this approach, large-scale practical problems can be solved exactly within very reasonable computation time. This makes the practical implementation of the dynamic group-testing scheme possible in manufacturing and health care settings.

AB - Group testing with variable group sizes for incomplete identification has been proposed in the literature but remains an open problem because the available solution approaches cannot handle even relatively small problems. This article proposes a general two-stage model that uses stochastic dynamic programming at stage 2 for the optimal group sizes and non-linear programming at stage 1 for the optimal number of group-testable units. By identifying tight bounds on the optimal group size for each step at stage 2 and the optimal initial purchase quantity of the group-testable units at stage 1, an efficient solution approach is developed that dramatically reduces both the number of functional evaluations and the intermediate results/data that need to be stored and retrieved. With this approach, large-scale practical problems can be solved exactly within very reasonable computation time. This makes the practical implementation of the dynamic group-testing scheme possible in manufacturing and health care settings.

U2 - 10.1080/0740817X.2010.504684

DO - 10.1080/0740817X.2010.504684

M3 - Journal Article (refereed)

VL - 43

SP - 69

EP - 83

JO - IISE Transactions

JF - IISE Transactions

SN - 2472-5854

IS - 2

ER -