Optimization for marketing allocation in R

Question

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().

Answer 1

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.

Answer 2

This is too complicated for a specific R function. Here is a suggestion for an algorithm which may sometimes work:

You should start by calculating $E_{n,f}$, the expected profit for each customer for each offer.

Then find the most profitable offer per customer, and rank the customers by profitability. If at least $b$ of these numbers are positive, choose the best $b$ of them; if at least $N-a$ are negative, choose the best $a$ of them; if they change sign between $a$ and $b$, just choose the positive profit offers.

That was the easy bit. You now have to deal with the total cost and the minimum percentages constraints. There is no easy way of doing this: you may have to try swapping offers or adding or removing them to bring the cost within the constraint or bring the percentages into line. I would suggest adjusting the offers in a way which moves towards the constraints when they are breeched and which, given the choice among customers and changes to offers, minimize the negative effect on expected profits, and then repeat until the constraints are met. I expect this does not guarantee reaching either a feasible solution or an optimal solution, and it may be slow.