Guest post by Bob Agnew (firstname.lastname@example.org)
Marketing optimization consists of assigning offers to prospects in order to maximize total expected profit subject to a few general linear constraints and the requirement that a prospect receives at most one offer. What distinguishes these problems is their sheer size. With millions of prospects, brute force linear solvers are unsuitable. On the other hand, a nonlinear collapsed dual algorithm works fine. The purpose of this post is to share an R-script which demos a very simple version of the algorithm with linear equality offer quantity constraints. We ran our demo problem previously in SAS using PROC NLP for dual minimization and it consumed about five minutes of CPU time on a large IBM server. Remarkably, the R version, using the nonlinear minimization function nlm, runs in about one minute on my home PC.
For the demo, we simulate an expected profit vector for each of three alternative offers across a million prospects. The simple offer quantity constraints sum to 600K so 400K prospects will receive no offer. The binary assignment problem is relaxed to a linear program and its dual linear program is collapsed to a simple function for minimization by nlm. The quasi-optimal dual variables are then employed to adjust the profit vectors and to rank-order the prospects for assignment. The actual offer assignment process is simple and straightforward. At the end, we compare total profit to the dual minimum which serves as an upper bound on any primal solution. The results are very close.
Link for Code
Link for Reference (previously linked on communities.sas.com/thread/4320)