DIMACS REU Summer 2008
Project title: Optimization of Sequencing and Threshold Levels of
Mentors: Dr. E. A. Elsayed and Dr. Ming Xie
Li, Christina Young, and Yada Zhu
Abstract: This project considers a problem of container
inspection at the port of entry. Every year, millions of containers
are imported overseas. These units must be deemed acceptable or
suspicious before entering the United States, but manually checking
each one is highly impractical. Thus, the shipments are subjected to
various forms of testing and then are either allowed to move freely
inside the country or be manually inspected. Testing checks for a
number of attributes that could indicate the potential presence of
illegal materials such as weaponry, contaminated food, and
drugs. Additionally, there are additional costs that come with errors
being made or multiple tests at particular sensors. The objective of
this project is to optimize the testing policies while minimizing
cr - cost of repeated inspections
mre - multiplier of repeated inspection error
pfa - probability of a false accept
pfr - probability of a false reject
- Week 1:
- Monday, June 2: Begin REU.
- Became familiar with work. Met with advisors and reviewed several
papers describing the problem. Became familiar with the "big picture"
of the project.
- As containers go through each sensor, measurements of different
attributes are made. Each sensor then makes a decision - accept the
container or reject it. Setting a threshold for the measurements works
well if the "good" and "bad" populations are well-separated, but what
if there is some overlap? Having a strict threshold level then causes
some errors to occur. Our solution is to incorporate a guard band that
makes no immediate decision, should the measurement fall within the
range. A second inspection is made, with a more accurate
measurement. Now a more strict threshold level can be applied.
- Week 2:
- Began a more thorough studying of the probability theory involved, with
special attention to conditional probability. Looked through the
formulas for both individual sensors and entire systems.
- Familiarized self with Matlab coding and saw how it was an implementation of the equations previously constructed. Reread sdf previous papers... many times.
- Week 3:
- Presented discussion topic to fellow undergraduate
- Adjusted variable values in Matlab code to see their
effect on inspection cost.
- Briefly, a change made to:
- bandwidth has a larger impact
- the cost of a false positive has a larger impact
- the standard deviation of the acceptable population has a larger impact
- the cost of a false negative has less impact
- the standard deviation of the unacceptable population has less impact
- the error of repeat inspections has less impact
- the error of initial inspections has medium impact.
- Week 4:
- Performed a more detailed analysis of each variable's impact on
the total cost. First kept three values fixed: the standard deviation
of the two populations as they go through each of the three sensors,
as well as the error of the initial readings at each sensor. These
values have been chosen such that the inclusion of a guard band
is an improvement over one without. The chosen values:
- sigma0 = [0.45 0.55 0.65]
- sigma1 = [0.3 0.2 0.26]
- sigmaErr = [0.08 0.1 0.11]
- Used Matlab to see effects of five different factors:
- bandwidth at levels 0.1, 0.2, and 0.25 (3 levels)
- cost of repeated inspections at levels 1.2 and 1.5 times the
original cost (2 levels)
- multiplier of repeat measurement error at levels 0.2 and 0.5 times
the original measurement error (2 levels)
- cost of false positive at levels 500 and 1000 (2 levels)
- cost of false negative at levels 10 million and 20 million (2 levels)
- All possible combinations (3*(2^4) = 48 combinations) of these five factors were put into a
table, and the results observed.
- Week 5:
Ran ANOVA tests to determine main effects of minimum cost, pfr, and pfa. Determined:
- For pfr, the bandwidth has most effect, increasing the probability
while increasing bandwidth
- For pfa, the bandwidth has most effect, decreasing the probability
while increasing bandwidth
- For minimum cost, the cfp has the most effect, increasing the
minimum cost as cfp increases
- Week 6:
- Attempted to modify current Matlab code so that minimum cost, pfr,
and pfa can be computed for n inspections. Not being terribly
proficient in Matlab, this has been quite challenging and
time-consuming. The equations used are significantly more complex and
require a great deal more care in creating the algorithm.
- Week 7:
- Prepared and gave final presentation
(click to download the presentation slides in pdf format).
- Week 8:
- An alternate code, based on earlier versions of the
single-repeat simulation, was created by Mingyu Li. Currently testing
to see effects of further inspections.
- The earlier, single-repeat code was updated to obtain a more
accurate measurement of each pfa and pfr.
- Friday, July 25: End REU.
Last updated: July 25, 2008, 20:26 by Robert Davis