Given the table
|------------|-----------------|-----------------|-----------------|
| Customers | Product A | Product B | Product C |
|------------|-----------------|-----------------|-----------------|
| a | 1.0 | 0.7 | 0.2 |
|------------|-----------------|-----------------|-----------------|
| b | 0.3 | 0.7 | 0.8 |
|------------|-----------------|-----------------|-----------------|
| c | 0.9 | 0.9 | 0.9 |
|------------|-----------------|-----------------|-----------------|
| d | 0.7 | 0.2 | 0.2 |
|------------|-----------------|-----------------|-----------------|
| e | 0.3 | 0.5 | 0.4 |
|------------|-----------------|-----------------|-----------------|
| f | 0.5 | 1.0 | 1.0 |
|------------|-----------------|-----------------|-----------------|
| g | 0.2 | 0.2 | 0.4 |
|------------|-----------------|-----------------|-----------------|
each customer's row contains the probability of purchasing the specific product.
I would like contact the least number of customers and achieving some (expected) number of sales for products A, B and C.
For example: given the table and the following requests
- Target for Product A: 1
- Target for Product B: 1
- Target for Product C: 2
would lead to the following solution:
- a -> Product A
- f -> Product B
- b, c, e -> Product C
so that out of 7 customers I could select just 5 of them and achieving the (expected) sales.
With several thousand of customers and more products the standard tools (I mainly used PuLP library) demand way too much time.
So my question is: given the special form of the problem are there faster algorithms for solving it or ways of solving the problem more efficiently?
Thanks.