Best split with conditions

Question

Given this sort of dataset:

ID	Score1	P1	Flag
id1	0.01	0.2	False
id2	0.99	0.9	True
...	...	...	...

The limitations of each variable are:

• ID: identifier if each object, unique in the table
• Score1: A number between 0 and 1, that represent the value of the object
• P1: probability of call, betwen 0 and 1
• Flag: should the object be in group <b?

I want to split the dataset in 2 groups (A and B) given the rules:

• The sum of P1 on group A should be at least n
• The sum of P1 on group B should be at least m
• The diference between the average Score1 in the two groups should be minimal
• The average of Score1 on all the selected (group A + group B) should be maximum
• We don't have to select all the rows
• Rows with Flag = True can not be in group A

How can I do this in a smart/fast way?

Answer 1

There is no efficient algorithm to do what you want, unless P=NP. In fact, there is no efficient algorithm to even decide whether a feasible partition of the dataset into two groups exists.

You can see this by reducing from the partition problem: Given a (multi-)set of positive numbers $X=\{x_1, x_2, \dots, x_n\}$ we want to decide whether there exists a subsets $S$ of $X$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$. Without loss of generality we can assume that $0 < x_i \le 1$ (by simply dividing all $x_i$ by $\max_{i=1, \dots, n} x_i$).

Then, for each $x_i \in X$ you can create a row in your dataset with:

• ID = $i$;
• Score = $0$;
• P1 = $x_i$;
• Flag = false.

Finally, pick $n = m = \frac{1}{2}\sum_{x \in X} x$.

A feasible parition into two groups $A$ a and $B$ induces a subset $S$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$. Specifically if $i_1, i_2, \dots, i_k$ are the IDs of the rows selected into $A$, you can define $S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$.

Conversely, given a set $S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$, you can select $A$ as the set of rows with IDs in $\{i_1, i_2, \dots, i_k\}$ and $B$ as the set of rows not in $A$.