1
$\begingroup$

The problem

You have a set on N (around 15-30) seemingly-identical objects, which in fact comprises a small number D (unknown, between 1-3) of defective objects and the rest (N-D) are good.

There is a test which can be performed on any chosen subset of the objects, which will reveal if the set contains at least one defective object. But the test is expensive, and only one test at a time can be carried out (multiple tests can't be run in parallel).

Your mission

Devise a testing strategy that will identify all defective objects as cheaply (on average) as possible. If there is a "well known" existing solution, that's fine, but I don't know it if so.

Origins of the problem

I have a new 18 core CPU that I'm overclocking core by core. A core that's overclocked will either be stable (its virtually never going to crash stuff running on it), or unstable (its likely to crash something running on it after a number of hours). The only way to test if the 18 cores are overclocked in a stable manner is to run a stress test program for some amount of time and see if it crashes or gives errors. Typically an hour under stress gives a good idea if any core will fail, but when you're done, you really need to stress test it for many hours if you want to be sure.

My current setup for the 18 cores runs nicely for an hour and I thought it was stable. But it failed when I tested it overnight for 12 hours. So 1 of the cores (or perhaps 2 or 3 at most) is in reality defectively tuned, although probably very close to correct.

I could try several things to find which core/s are defectively tuned.

  • I could slightly unstress all but one core, for all 18 cores in turn, and run it for 18 x 12 hours at a time, and that would definitely reveal any defectively tuned cores.
  • I could do the above, but when I find and fix any defectively tuned core, add an extra test run for 12 hours with all 18 cores stressed. That adds 1-3 x 12 hours of full retests, but also means if the mistuned cores happen to be 1+2, I don't waste 16 x 12 hours testing good cores after all the mistuned ones are fixed.
  • I could test say 2 or 3 cores at a time for 12 hours. So I slightly unstress all but cores 1-3 and see if that works for 12 hours; there's low-ish odds that any specific group of 2-3 cores contains a mistuned core (and very low odds it contains >1 mistuned core), and this could eliminate 2-3 at a time not 1. The downside is, when a test crashes, I have to add further tests to find which core/s of those 2-3 were mistuned, it isn't immediately obvious.
  • And so on.....

The trouble is, I don't really want to spend 3 weeks solid testing this thing. SO I'm looking for a better strategy.

The stated problem abstracts this situation, with N = 18, D is probably between 1 and 3, and the "cost" of a test is the time taken to thoroughly stress test for 12 hours, any selected subset of the 18 cores in the CPU.

(The problem simplifies somewhat by ignoring the option to do shorter or longer tests - for example test everything for 4 hours and see if that shows up defective tuning, then test for 12 hours to be sure. To an extent that can be modeled as a "cost" or 4 hours per test plus a 12 hour confirmatory run at the end. The reason is, I'm not certain that success/fail on a 12 hour run can be modelled as equivalent to 12 sequential 1 hour runs, statistically)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ For the puzzle part, when you have a reliable but expensive yes-no test, looking for a single defective item is most effectively done by halving the sample size at each trial. As for the real world part, I'm not entirely convinced you have a reliable test available, or even that you are approaching the goal of buying reliable cpu cycles in an altogether sensible manner. $\endgroup$ – Bass Apr 13 '20 at 11:25
  • $\begingroup$ Is that still the case when the number of defective items may not be 1? And yes,it's not a reliable test but really none is. But it can be idealised as one, creating an approach and a puzzle. $\endgroup$ – Stilez Apr 14 '20 at 9:19
  • 2
    $\begingroup$ Does this answer your question? Wolves and sheep $\endgroup$ – melfnt Apr 14 '20 at 11:52
  • 1
    $\begingroup$ I don't think the referenced question actually answers this one. It is an excellent answer to finding 5 bad among 100, and gives some information on how that solution was found, but there is no generalized method given there that can easily be purposed to the present task (in fact, the best answer relies on a "block" whose derivation is neither given nor even hinted at, but that "block" is actually the crucial operational component of that solution). $\endgroup$ – Rubio♦ Apr 14 '20 at 15:58
  • 1
    $\begingroup$ group testing $\endgroup$ – RobPratt Apr 15 '20 at 0:41
2
$\begingroup$

This type of problem is known as group testing, and you can find more information in the Wikipedia page.

Improve this answer
$\endgroup$
2
$\begingroup$

To expand on RobPratt's sort-of-answer, and to repeat some of my own answer to Wolves and Sheep...

You have 18 items, of which "3 or fewer" are defective, and you want to minimize the number t of tests to identify all of the defective items. Imagine your testing strategy as a matrix of 0s and 1s with 18 columns and t rows. The 1s in the ith row indicate which of the 18 items you should include in the ith test.

Define the "sum" of a set of columns as being the bitwise-OR of those columns. You want to find an 18-by-t matrix such that each combination of 1, 2, or 3 rows has a distinct sum.

The math-jargon term for this is that you want to find a "$\overline 3$-separable matrix" with 18 columns.

Unfortunately, all the mathy research papers here focus on construction techniques for very large n (like, if you had a few thousand or a few million CPUs to test, of which only 3-or-fewer were bad). I'm not aware of any comprehensive listing of known small solutions. When I was working on "Wolves and Sheep" I even went so far as to get a copy of the CRC Handbook of Combinatorial Designs, but it did not prove helpful.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.