A more efficient way of solving an peculiar optimization problem

Question

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.

Answer 1

This problem is actually not an assignment problem but a set covering problem.

Let's say that choosing customer $i$ is represented by $x_i=1$ when chosen, $0$ otherwise. Let's say $t_j$ are the sales targets for your products and $d_{ij}$ is the "demand" or probability to sell product $j$.

\begin{align} \min&\quad\sum_i x_i \\ \text{s.t.}&\quad \sum_i d_{ij} x_i \geq s_j \quad\forall j\\ &\quad x_i\in\{0,1\} \quad\forall i \end{align}

The objective tells us you want to minimize the customers you contact. The last line tells us that you can either contact or not contact a customer, but you cannot contact them 50%. The middle constraint tells us, that the sum of the probabilities of buying of the contacted customers are at least your sales targets.

This problem is NP-hard. (Choose $s_j = 1$ and $d_{ij} \in \{0,1\}$ for a reduction to set covering.) It is therefore not a transportation problem, cannot be solved with the simplex algorithm because of the last condition, and any polynomial time algorithm is unlikely to exist. However, any MIP solver (CPLEX, Gurobi, SCIP) can handle even large instances of any set covering problem.

It is NP-hard to approximate with a factor better than $\mathcal O(\log n)$. There is an easy greedy algorithm that achieves that ratio:

• Start with an empty solution and add customers one by one until your sales targets are satisfied. Always pick the customer that covers the most uncovered demands.

• Given the demands $p_j$ you already have for each product, the uncovered demand for a customer $i$ can be computed by $\sum\limits_j \max\{\min\{d_{ij}, s_j\}-p_j,0\}$.