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?



1 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\}$.

  • $\begingroup$ Thanks @Luke599999. May I use some approximation algorithm? $\endgroup$
    – dgamboz
    Jun 18, 2020 at 11:05
  • 1
    $\begingroup$ I added a paragraph about approximation. $\endgroup$
    – PSLP
    Jun 18, 2020 at 11:23
  • $\begingroup$ I don't really think i understand the question. But I think this is a completely new question and you should post it as a new question. $\endgroup$
    – PSLP
    Jun 18, 2020 at 16:12
  • $\begingroup$ Can the greedy algorithm be applied to the same problem with a new constraint for which I can propose just one product to each customer? In formula: $$ \min \sum_{ij}x_{ij} $$ $$ s.t. \sum_i d_{ij} x_{ij} \ge s_j \forall j $$ $$ x_{ij} \in \left\{0,1 \right\} $$ $$ \sum_j x_{ij} <= 1 $$ (sorry for the previous unclear comment, I was having troubles editing it...) $\endgroup$
    – dgamboz
    Jun 18, 2020 at 16:22
  • 1
    $\begingroup$ or.stackexchange.com/questions/4409/… $\endgroup$
    – dgamboz
    Jun 19, 2020 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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