Optimal sequential inspection policies

Endre Boros, Noam Goldberg, Paul B. Kantor, Jonathan Word

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We consider the problem of combining a given set of diagnostic tests into an inspection system to classify items of interest (cases) with maximum accuracy such that the cost of performing the tests does not exceed a given budget constraint. One motivating application is sequencing diagnostic tests for container inspection, where the diagnostic tests may correspond to radiation sensors, document checks, or imaging systems. We consider mixtures of decision trees as inspection systems following the work of Boros et al. (Nav. Res. Logist. 56:404-420, 2009). We establish some properties of efficient inspection systems and characterize the optimal classification of cases, based on some of their test scores. The measure of performance is the fraction of all cases in a specific class of interest, which are classified correctly. We propose a dynamic programming algorithm that constructs more complex policies by iteratively prefixing devices to a subset of policies and thereby enumerating all of the efficient (i.e., undominated) inspection policies in the two dimensional cost-detection space. Our inspection policies may sequence an arbitrary number of tests and are not restricted in the branching factor. Our approach directly solves the bi-criterion optimization problem of maximizing detection and minimizing cost, and thus supports sensitivity analysis over a wide range of budget and detection requirements.

Original languageEnglish (US)
Pages (from-to)89-119
Number of pages31
JournalAnnals of Operations Research
Issue number1
StatePublished - Jul 2011

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research


  • Bi-objective optimization
  • Dynamic programming
  • Port security
  • Sequential inspection


Dive into the research topics of 'Optimal sequential inspection policies'. Together they form a unique fingerprint.

Cite this