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

Jiejian FENG, Liming LIU, Mahmut PARLAR

Research output: Journal PublicationsJournal Article (refereed)

6 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
Number of pages15
JournalIISE Transactions
Volume43
Issue number2
DOIs
Publication statusPublished - 2010
Externally publishedYes

Fingerprint

Testing
Nonlinear programming
Health care
Dynamic programming

Keywords

  • Group testing
  • incomplete identification
  • variable sizes
  • dynamic policy
  • stopping rule
  • bounds

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.",
keywords = "Group testing, incomplete identification, variable sizes, dynamic policy, stopping rule, bounds",
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)

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.

KW - Group testing

KW - incomplete identification

KW - variable sizes

KW - dynamic policy

KW - stopping rule

KW - bounds

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-78650672448&doi=10.1080%2f0740817X.2010.504684&partnerID=40&md5=297df9cc9a3ba48fe139bc22117e6196

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 -