Many businesses send targetted special offers to their customers. Doing this in an optimal way is hard, but valuable. Here is an animated demo that illustrates some ideas around how to optimize the targetting of offers, combining both mathematical optimization techniques (computationally expensive) and rules of thumb (quicker but less precise).

The Demo

The demo panel above is a live, working example that implements several algorithms for allocating offers to customers. Click on the buttons at the top to run the demo. To find out wwhat is happening here, read on.

The Problem

This example is taken from the credit card industry (which is concerned with serving both cardholders and the merchants that accept the cards), but the basic ideas apply to any industry.

The key issue here is that you want to send special offers that are relevant to customers, but you can't send every offer to everyone, and coming up with the right combination of offers for each customer is hard, especially in real time:

So this demo illustrates a possible approach to allocating offers, that balances accuracy (achieving the true optimium) with feasibility (doing it fast enough to work in a high-transaction environment, possibly even in real time).

Elements of the demo, and what the buttons do

Generating data

The first button generates a new random set of 500 random customers (circles in the large panel on the left), 10 merchants, and 3 offers per merchant (offers are shown as dots in the top right panel). The size of each customer represents customer value (total spend), and the colour of each offer dot represents value of the offer (blue is low, red is high, in a continuous spectrum).

Obviously, in a real setting, there will be a lot more customers, merchants, and offers, which makes the optimization much more difficult and time-consuming, which is what makes the hybrid optimization/rules of thumb approach described here interesting.

Allocation strategy buttons

Clicking on the remaining five coloured buttons runs one of five allocation algorithms:

The five strategies are:

  1. Random randomly allocates the offers to customers, subject to some constraints (explained below)
  2. Smart C targets high value customers first, i.e., it goes through the offers in random order, and allocates them to the highest value customers first, subject to the constraints
  3. Smart O targets the customers in random order, but allocates high-value offers first
  4. Smart C+O is a combination of the two "smart" algorithms, targets the highest-value customers first, and allocating the high-value offers first
  5. Optimize performs a true optimization, allocating whichever offers to whichever customers, in order to realize the highest possible total value, subject to the constraints. It does this by formulating the problem as a linear program, and using an external solver (GLPK) to come up with the true optimum, the very best value that can be obtained for this data set


All of these algorithms obey the following constraints:

The graph: What we're trying to maximize

Each time you click a button, a bar is added to the bar graph at the bottom right. This measures total value created; in this simple demo, this is computed as the sum of offer value X customer value across all the offers allocated (the idea being that an offer will yield more value if a high-value customer takes it than a low-value customer, and higher value offers yield more benefit than low value ones).

Of course, the metric we optimize can and should be a lot more sophisticated, including measures of customer equity or customer lifetime value.

Lessons Learned

This demo was designed to explore how close we can get to the optimal allocation, by using quick rules of thumb rather than a full optimization each time. The results are promising:

  1. The random allocation (grey button) produces a starting point, and is different each time; we are trying to improve upon this scatter-gun approach
  2. The optimal allocation (blue button) produces the best possible outcome, and yields the same result each time; it also takes about 30 times longer than the other algorithms (notice the time in milliseconds below the bar on the graph)
  3. The Smart C allocation is usually (not always) better than random, but not as good as optimal, and Smart O performs even better than Smart C; both are even faster than Random, and much faster than Optimal
  4. Smart C+O performs much better than either Smart C or Smart O alone, and is usually very close to Optimal, but much faster

The big take-away here is that optimization is useful (even essential) to understand the best results possible for such a problem, but heuristics (simple rules of thumb) can get you most of the way there, at much lower cost (i.e., much faster computationally). But you would never know they worked if you did not have a way of determining the optimum.

Taking it forward

The logical next step would be to apply this to a market, and use optimization to calibrate a set of simpler rules that achieve close-to-optimal results at much lower cost. A key part of this process would be coming up with a reliable way of measuring the value of the offers program, akin to a customer lifetime value or customer equity approach.

Doing this correctly could deliver huge value, and be at the core of an intelligent and adaptive marketing approach.

Add a comment