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.