Solved – Optimization for marketing allocation in R

optimizationr

Are there any tools in R that could be used to optimize the allocation of customers amongst possible offers, given constraints? Can anyone give hints/examples on their use? Hope my setup makes sense…

Here is the problem setup:

There are the following:

  • $N$ customers ($N$ is large)
  • $F$ offers (the offers that can be made to a customer; $F$ is relatively small)
  • $P_{nf}$ — the probability of acceptance of offer $f$ by customer $n$
  • $D_{nf}$ — the expected monetary value if customer $n$ accepts offer $f$
  • $C_f$ — the cost of offering offer $f$ to any customer
  • $E_{nf}$ — the expected profit of offering offer $f$ to customer $n$ ($P_{nf} D_{nf} – C_{f}$)

Constraints:

  • Each customer can be allocated to only 1 offer (not every customer need receive anything).
  • The total number of offers made (call it $T$) between a and b.
  • The total cost $TC<c$.

The percentage of $T$ comprised by each offer $f$ is $\geq d$. This means that sometimes an offer has to be made at least $d$ times. There is one of these rules for each offer.

Goal:

  • Maximize profit.

Anything in R?

EDIT:

  • I wonder about using something along the lines of http://cran.r-project.org/web/packages/Rglpk/index.html
    which appears to support "large" problems and the types of constraints I have.
    Of course, "large" in the context appears to be much less than the millions for N I have.

  • One thought I had was to caculate the expected profit for each customer and each offer. Then, run a clustering algorithm (row = customers and columns = expected profit for each promotion) like k-means with k large (e.g. 1,000). Then assign each of the customers into a cluster and use the cluster centroid as the value of the expected profit for the optimizer.

EDIT AGAIN

For the sake of helping others, the conclusion I came to was to indeed cluster the customers and then use a standard linear solver (I got lpSolve in R to work well).

The other option is to use a non linear approximation. Robert Agnew helped me tremendously on this question – using his dual formulation. See this post. His R script is also linked and works great – changing from equality constraints for the offer quantity to inequality constraints requires use of nlminb().

Best Answer

This is a typical linear programming problem, where both objective and constraints are linear. R has many functions to solve this, for example optim() or package BB. However your decision variables are binary and N is probably big. So you may want to try to solve the dual problem, instead of solving the primal directly.

Related Question