1

I have boolean variables for the population of many towns. And I want to create an application where a user can type in a percentage corresponding to the variable's true value, and I want to get the biggest possible population that satisfies that proportion

Let's say for example in Town 11 I have

  • Town population (population): 1295
  • People where variable diabetes is true (pop-true): 575
  • People where variable diabetes is false (pop-false): 720

And my user selected for variable diabetes, 0.2 (percentage)

This means that I want the biggest subset of this town population that still satisfies the condition that 20% of the subset has diabetes.

For this I have already the following algorithm:

if(percentage >= (pop-true/population)){
   max_people = pop-true/percentage
}else{
   max_people = pop-false/(1 - percentage)
}

In this example max_people = 720 / (0.8) = 900

So for the diabetes the biggest possible population to satisfy the "20% of people have diabetes" is 900. A group with 180 people with diabetes and 720 people without.

However, I don't have only one variable, but four. diabetes, obesity, over 65 and health worker variables for this particular town.

And my users will have 4 input fields, to select a percentage for each variable - but independent from each other, for example:

[0.2, 0.15, 0.6, 0.1] would mean:

  • 20% of people with diabetes
  • 15% of people with obesity
  • 60% of people are over 65
  • 10% of people are health workers

I need to expand this algorithm to make it calculate what's the maximum amount of people that would satisfy all the user inputted proportions at once. Taking into consideration that I have the data in a dis-aggregated fashion.

Town diabetes obesity over 65 health worker Population
11 0 0 0 0 100
11 0 0 0 1 200
11 0 0 1 0 50
11 0 0 1 1 30
11 0 1 0 0 100
11 0 1 0 1 200
11 0 1 1 0 30
11 0 1 1 1 10
11 1 0 0 0 50
11 1 0 0 1 25
11 1 0 1 0 230
11 1 0 1 1 95
11 1 1 0 0 100
11 1 1 0 1 35
11 1 1 1 0 10
11 1 1 1 1 30

I already built an intuition to check whether certain values are true. "What is the maximum amount of people where percentages = [0,0,0,0]?" should be 100 (as there is only one possibility for this combination in the dataset)". Similarly, for [1,1,1,1] it should be 30, and the same for all 0,1 percentages.

For [0,0,0,0.1] (0% diabetics, 0% obese, 0% over 65 and 10% health workers), we know this combination of no-diabetes, no-obesity, under-65 and non-health worker - group that contain 100 people - has to correspond to 90% of the total, so then 10% of the group to be health workers, the maximum amount of people satisfying this conditions is 100/0.9 = 111.111...

How to expand/generalize this algorithm to make it validate across all the variables? I don't mind an answer with pseudo-code

11
  • @Heagon It represents the amount of people to which the values are true. For example the first line means: "In town 11, there are 100 people that at the same time are not diabetic, not obese, are under 65 and are not health workers" The second line means: "In town 11, there are 200 people that at the same time are not diabetic, not obese, are under 65 and are health workers"
    – steps
    Dec 14, 2020 at 22:59
  • Why is it the maximum amount of people? Don't you mean minimum number of people to meet all of the criteria?
    – Dan Weber
    Dec 15, 2020 at 4:14
  • Or are you trying to determine the minimum number of people required when population is a fixed value?
    – Dan Weber
    Dec 15, 2020 at 4:15
  • Is diabetes 20% meaning that the sample cannot have more than 20% diabetes or less than 20% diabetes?
    – Dan Weber
    Dec 15, 2020 at 4:21
  • 1
    You need to clarify the rounding rules, as we can’t include people partially. So, how close should you stay within the given percentages? Dec 16, 2020 at 19:30

1 Answer 1

2
+50

You can formulate this problem as a Linear Program (LP).

You have 16 variables x0000, x0001, x0010, ..., x1111. That's one for each population group. For example, variable x0010 represents how many people we'll select from the group that has diabetes:0, obesity:0, over65:1, healthworker:0.

The objective is to select the maximum number of people summed over all groups:

max x0000 + x0001 + x0010 + ... + x1111

As constraints, you cannot exceed the given number of people in each population group:

x0000 <= 100
x0001 <= 200
x0010 <= 50
...
x1111 <= 30

Additionally, you have constraints for the proportions (compared to the total selected population):

/*Proportions*/
x1000 + x1001 + ... + x1111 = 0.2 * (x0000 + x0001 + x0010 + ... + x1111)
x0100 + x0101 + ... + x1111 = 0.15 * (x0000 + x0001 + x0010 + ... + x1111)
x0010 + x0011 + ... + x1111 = 0.6 * (x0000 + x0001 + x0010 + ... + x1111)
x0001 + x0011 + ... + x1111 = 0.1 * (x0000 + x0001 + x0010 + ... + x1111)
/*Reverse proportions*/
x0000 + x0001 + ... + x0111 = 0.8 * (x0000 + x0001 + x0010 + ... + x1111)
x0000 + x0001 + ... + x1011 = 0.85 * (x0000 + x0001 + x0010 + ... + x1111)
x0000 + x0001 + ... + x1101 = 0.4 * (x0000 + x0001 + x0010 + ... + x1111)
x0000 + x0010 + ... + x1110 = 0.9 * (x0000 + x0001 + x0010 + ... + x1111)

The first row says that the sum of selected people that have diabetes must equal 0.2 times the total number of selected people. The left-hand side of the first row contains all 16 variables, the first 8 ones representing x1000, x1001, ... where the first digit equals 1. Those are the variables for diabetes:1. The left-hand side of the second row contains all variables for obesity:1 and so on. Then, the latter 8 ones represent the reverse, for all values where obesity:0, diabetes:0, and so on.

Note: you have specified in some comments that these constraints must be equality constraints. In some cases, this might lead to an infeasible solution. You might want to use <= constraints to avoid this (as already suggested by Dan Weber in some comments).

Now you have the variables, objective and constraints of your linear program. There is existing software that can solve these types of problems for you. For example, you could use Microsoft Excel's solver add-on to do this.

Most existing software will even let you specify the additional constraint that the number of selected people must be a whole number (integer). In that case, your problem becomes an Integer Program (IP).

4
  • This approach solved the problem. I managed to write a solver in the LP File Format and run it thru the lpsolve (lpsolve.sourceforge.net). The only correction I have to make from your answer is that in order for the Linear Program to find a solution it had to also contain the "reverse" proportions. So not only the four left hand side where variable:1, but also when variable:0 and the opposite % (0.8 people don't have diabetes).
    – steps
    Dec 18, 2020 at 12:05
  • Now my challenge is how to make this work on a browser - as the only Javascript Linear Solver package I could find (jsLPSolver) doesn't work with this input that has variables on the left and right hand side of the constraints
    – steps
    Dec 18, 2020 at 12:22
  • 1
    Tip: you can subtract the right-hand side from the left-hand side of each constraint. The first constraint is equivalent to -0.2 * (x0000 + ... + x0111) + 0.8 * (x1000 + ... + x1111) = 0. Hopefully this can help you with jsLPSolver.
    – Thomasky
    Dec 18, 2020 at 14:19
  • Thanks for the tip. But then, when I move everything to the left, it complains of multiple variables on both side. I know I can subtract like x1000 - 0.2 x1000 = 0.8 x1000 But I wanted to avoid implementing that subtraction
    – steps
    Dec 18, 2020 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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