Mathematical Optimization Problem

[GasX]

Let me provide an example of the type of problem I am looking at.

Lets say you are trying to identify the sex of each person in a group of 100 people. (or as many as possible)
30% can be identified by looking at their hairstyle. It takes 30 seconds to analyze this attribute.
40% can be identified by their shoes. It takes 1 minute to evaluate this attrbute.
20% can be identified by their jewelry. It takes 10 seconds to analyze this attribute.

What is the fasted way to analyze this population?
What order of tests produces the best results?

Is there a formal approach to take to determine the answer to these questions? The real life situation being pursued is a dynamic one where there could be as many as a dozen tests and a good systematic approach is needed beyond trial and error.

Thanks In Advance

 

[her209]

The answer is to scream, "Mouse!"

 

[GasX]

Mouse in house?
Mouse has spouse
spouse takes house

amusing, but not particulaly effective...

 

[FiddleDD]

when my son gets on messenger later I will ask him...he is a phd student in math...and ranked very high on the putnam exam...

 

[GeneValgene]

assuming those are the only sex tests possible, i would guess that the fastest way to analyze the population is go from the fastest test to the slowest test.

hairstyle->jewelry->shoes

 

[PlasmaBomb]

Write the code so it is threaded, therefore on a dual core you get best results in a minute...

Start -
Thread 0 - Shoes - Complete in 1 min
Thread 1 - Jewlery - Complete in 10 sec - Hairstyle - Complete in 30 sec

Total compute time - 1 minute...

 

[Legendary]

shortest test first

since there can be overlap, but the overlap %s are undetermined, you have to do the shortest test first and hope for the best

 

[DrPizza]

I'm not sure if I understand the original question. Is it 30 seconds person? Or 30 seconds to analyze all 100 people? I guess the problem would be too trivial if it was 30 seconds for the entire group, i.e. you'd have to run all 3 tests. Thus it'd take the same total time regardless of the order of the tests.

If I understand the problem correctly, then here's how each would work out:

hair, then shoes, then jewelry:
100(30) +[(1-.30)100](60) + [(1-.30)(1-.40)(100)](10)
i.e. 30 seconds each for 100 people, 60 seconds each for approximately 70 people (70% of 100 people who haven't been identified), and 10 seconds each for 42 people(who haven't yet been identified) = 7620 seconds

jewelry, hair, shoes
100(10)+[(1-.20)100]30+ [(1-.30)(1-.20)(100)](60) = (100 people)(10 seconds per person) + (80 people)(30 seconds per person) + (56 people)*(60 seconds per person) = 6760 seconds

I'm not doing all of the possible orders. And I very likely made some sort of careless mistake. Actually, I did make a careless mistake: I had 20 seconds per person for jewelry. And, if that's the case, then the total time was 7760 - more than the hair, shoes, jewelry order (and showing that quickest first isn't necessarily best.)

As far as a good systemic approach; I'm not thinking of anything at the moment; I've never run into a problem like this before. With 12 different tests, there would be 12 factorial possible orders of the tests, thus it'd be ridiculous to attempt to do this by hand. However, the problem lends itself quite easily to writing a computer program to solve it, which would do so in a second or two. Writing a program would probably take 10 minutes or less. In the future, when faced with more or a different set of tests, you could probably more quickly edit the test (or change the inputs) faster than you could analyze it by hand.

 

[GasX]

DrPizza - you got the gist of it.

Some empirical testing showed that the intuitive answer is not always the optimal solution (i.e in some cases neither the fastest first or the highest percent first and following in descending order is the best solution). This is why I am looking for the best approach. If there is a way to automate the analysis, then it would be something with an immediate practical application.

 

[mjrpes3]

nvm.

 

[mjrpes3]

[hair,shoes,jewelry] TOTAL TIME: 7620
[shoes,hair,jewelry] TOTAL TIME: 8220
[hair,jewelry,shoes] TOTAL TIME: 7060
[jewelry,hair,shoes] TOTAL TIME: 6760
[shoes,jewelry,hair] TOTAL TIME: 8040
[jewelry,shoes,hair] TOTAL TIME: 7240

 

[Random Variable]

multiobjective linear program?

let x = the number of people whose hairsytle is analyzed
let y = the number of people whose shoes are analyzed
let z = the number of people whose jewelry is analyzed

min 30*x+y+10*z
max 0.3x+0.4y+0.2z
such that x+y+z=100

the units might not be right, though

I would then use the method of goal programming to find the "best" solution.

 

[rgwalt]

This problem may be like the traveling salesman problem, or the knapsack problem. In order to find the true optimum order of testing, you have to check each possible order. However, you may be able to find a good local optimum by using one of the methods mentioned in the thread, like ordering your tests in order of increasing time, or decreasing percentage.

Or, multiply time taken by (100-%identified) and order from lowest to highest. Again, this may not produce an optimal result, but it could provide a consistantly good local optimum.

R

 

[mjrpes3]

Interesting...

----------------------------------------------

a: 20% discovery, 40s/person
b: 30% discovery, 60s/person
c: 40% discovery, 80s/person

[b,c,a] TIME: 13280
[c,b,a] TIME: 13280
[c,a,b] TIME: 13280
[a,c,b] TIME: 13280
[b,a,c] TIME: 13280
[a,b,c] TIME: 13280

-----------------------------------------------

a: 20% discovery, 20s/person
b: 30% discovery, 30s/person
c: 40% discovery, 40s/person

[b,c,a] TIME: 6640
[c,b,a] TIME: 6640
[c,a,b] TIME: 6640
[a,c,b] TIME: 6640
[b,a,c] TIME: 6640
[a,b,c] TIME: 6640

 

[mjrpes3]

a: 20% discovery, 10s/person
b: 30% discovery, 15s/person
c: 40% discovery, 20s/person

[b,c,a] TIME: 3320
[c,b,a] TIME: 3320
[c,a,b] TIME: 3320
[a,c,b] TIME: 3320
[b,a,c] TIME: 3320
[a,b,c] TIME: 3320

There seems to be a pattern

 

[rgwalt]

Originally posted by: mjrpes3
a: 20% discovery, 10s/person
b: 30% discovery, 15s/person
c: 40% discovery, 20s/person

[b,c,a] TIME: 3320
[c,b,a] TIME: 3320
[c,a,b] TIME: 3320
[a,c,b] TIME: 3320
[b,a,c] TIME: 3320
[a,b,c] TIME: 3320

There seems to be a pattern

Well, in all your examples, the % and times are linear combinations of each others, so the fact that it doesn't matter which order you pick is no surprise.

 

[mjrpes3]

So to get the fastest time, order the groups by doing the following:

1. For each group, divide chance of discovery by rate per person, giving you a constant
2. Order the groups by constant, highest value first

 

[mjrpes3]

Originally posted by: rgwalt

Well, in all your examples, the % and times are linear combinations of each others, so the fact that it doesn't matter which order you pick is no surprise.

It was a surprise to me but makes sense in retrospect.

 

[mjrpes3]

Originally posted by: mjrpes3
So to get the fastest time, order the groups by doing the following:

1. For each group, divide chance of discovery by rate per person, giving you a constant
2. Order the groups by constant, highest value first

So does this seem right to everyone else?

 

[FleshLight]

Just write a linear program.

1. define optimization equation (30x + 60y + 10z = minimize)
2. define constraints (x = .30, y = .40, z = 0.2)
3. define nonzero variables (x,y,z >= 0)

Use matlab/excel/mathematica/whatever to solve.

 

[Cattlegod]

infinite. even in the best case that there are no overlaps, 10 people will still be binned as 'pats'

 

[gevorg]

Originally posted by: FleshLight
Just write a linear program.

1. define optimization equation (30x + 60y + 10z = minimize)
2. define constraints (x = .30, y = .40, z = 0.2)
3. define nonzero variables (x,y,z >= 0)

Use matlab/excel/mathematica/whatever to solve.

:thumbsup:

 

[GoingUp]

Have everyone drop their pants and underwear.

 

[GasX]

Originally posted by: gevorg

Originally posted by: FleshLight
Just write a linear program.

1. define optimization equation (30x + 60y + 10z = minimize)
2. define constraints (x = .30, y = .40, z = 0.2)
3. define nonzero variables (x,y,z >= 0)

Use matlab/excel/mathematica/whatever to solve.

:thumbsup:

WAY too much effort. This has to be done dynamically as the equations will change for each instance and there will be 6-10 runs per day.

 

[sactoking]

Originally posted by: Mwilding

Originally posted by: gevorg

Originally posted by: FleshLight
Just write a linear program.

1. define optimization equation (30x + 60y + 10z = minimize)
2. define constraints (x = .30, y = .40, z = 0.2)
3. define nonzero variables (x,y,z >= 0)

Use matlab/excel/mathematica/whatever to solve.

:thumbsup:

WAY too much effort. This has to be done dynamically as the equations will change for each instance and there will be 6-10 runs per day.

Excel Solver is the answer. It's simple and it does exactly what you want it to.