Using Linear Programming to Solve Direct Mail Allocation Problems
Authors: Elizabeth Mejia-Ricart and Ben Peters
In the part one of this two part series, we discussed how direct mail plays a role in credit card marketing campaigns, as well as how lenders determine which customers gets that direct mail. Now, it’s time to take your knowledge to the next level — we’re going to deep dive into the technical details* of Linear Programming, which is used to optimize allocation of direct mail for marketing campaigns.
- Note to the reader: this blog includes more technical details than our usual fare, but we hope you will come away with an understanding of how linear programming works.
This deep dive will answer the first question posed in the previous blog:
How do we help lenders decide how much direct mail is optimal to send to each segment?
Linear Programming Example
To make things easier, let’s walkthrough an example.
Suppose a lender has identified two customer segments — how should they allocate marketing spend? How many pieces of mail should they send to each segment?
The first aspect of this problem relies on what metrics the lender is interested in optimizing, which often rely on profitability.
For example, some lenders are interested in maximizing their total return on investment or ROA defined as present value (PV) of a customer segment divided by the cost to acquire (CTA) that segment. The CTA relates to how much money the lender must spend in mail pieces to acquire a customer in a particular segment. Some customers are more costly than others, as cost is dependent on how responsive the customer is to direct mail offers.
You’ll note that to make the most out of your total ROA, you could just send an infinite amount of mail to each customer segment as doing so will just keep increasing the total ROA. This is where constraints kick in.
Since the lender has limited resources, they can’t send an infinite amount of mail, as each piece of mail has a price tag associated to it. Moreover, there are only so many customers in each segment. The return of sending mail has a natural ceiling based on the number of customers available to acquire.
Thus, for the two segments in this example, this problem can be represented by the following statements:
Maximize total ROA → PV/CTA
s.t.¹ max. budget and max. customers in segments 1, 2
¹In mathematical notation, “s.t.” stands for “subject to”.
What does that mean? The above says to maximize total ROA, you look at PV divided by CTA based on the maximum budget and number of customers in the two example segments.
Now, suppose we’ve been assigned a budget of $10k for marketing spend to be distributed among the two segments. Additionally, suppose the cost per mail piece (CPM), or the cost to mail each offer, is $1.
Suppose we did previous analysis and determined the PV for each customer was determined to be $100 and $120 per customer in segments 1 and 2, respectively. The CTA for each customer in segment 1 is $100, which means that 1 out of 100 mail pieces will result in a customer acquisition. Further suppose the CTA for segment 2 is $150. Lastly, assume there are 50 customers that could be acquired in each segment.
Below summarizes the assumptions and numerical constraints for this example scenario:
Rank Ordering Algorithm Solution
One approach to solving the problem above is using a rank ordering algorithm. After calculating the ROA, the lender should send the maximum pieces of mail to the segment with the highest ROA, then move on to the next segment until they either meet one of the two constraints: (1) maximum budget or (2) maximum customers, whichever one happens first.
In this example, applying the rank ordering algorithm will result in the following solution:
(1) Send mail to all customers in segment 1:
- 50 customers with a $100 CTA results in $5k of the budget used, which translates into 5000 mailed pieces.
(2) Allocate the remaining budget to segment 2 or the budget necessary to acquire the maximum number of customers in segment 2, whichever is more constrained.
- Approximately 33 customers, based on the remaining budget of $5k and $150 CTA for segment 2, are acquired if the full $5k is used.
- Since there are 50 customers in segment 2, we’ll send out 5000 pieces of mail to use our remaining $5k budget.
(3) This gives us a total ROA of $9k.
We have solution, but the question becomes — is rank ordering the best way to allocate direct mail to customers?
While the rank ordering algorithm delivers good results in a multitude of scenarios, there is a big limitation encountered when using this approach. Once we increase the number of segments or the number of constraints to be considered a problem (which often is the case in real-world applications), this algorithm becomes increasingly cumbersome to use.
What optimization method can we use that’s more agile and efficient, regardless of constraints?
Introducing Linear Programming: A More Efficient Solution
There’s a more efficient way to solve the direct mail allocation problem. Let’s introduce mathematical notation to make our ability to solve the problem much more versatile.
Specifically, we can formulate the problem as a linear program (LP). Let x₁ and x₂ represent the mail sent to segments 1 and 2, respectively. Then, going back to our walkthrough example, our problem can be stated as:
- Total ROA, weighted by segment ROA, limited by to the total budget constraint: Max. x₁ + 0.8x₂, s.t. x₁ + x₂ ≤ 10000
- Maximum mail for segment, based on number of customers times mail pieces per customer: x₁ ≤ 50⨉ 100 = 5000
- Maximum mail for segment 2: x₂ ≤ 50⨉ 150 = 7500
- Assuming x₁, x₂ integers
Translated, this means that the maximum total ROA is based on the weighted sum of the two segments relative to their individual segment ROAs, all dependent on the total budget of $10k. Solving the two equations for total ROA and total budget constraint gets us the maximum mailed pieces for segments 1 and 2. This is equal to the number of customers times pieces of mail per customer. The above also specifies that the number of direct mail pieces must be integers (i.e., a whole number).
Why is this considered a linear program?
Because the constraints are linear combinations of the decision variables (i.e., the variables (x₁, x₂) are multiplied by a constant and added together).
In the case of two variables, these constraints can be represented as a two-dimensional plane, and this plane can be used to solve the problem if we follow four simple steps:
(1) Maximum budget constraint: x₁ + x₂ ≤ 10000.
Every pair of integers in the orange shaded area in the animation above are possible combinations that satisfy the total budget constraint, or the feasible region. If this were our only constraint, we could maximize our value by picking x₁ = 10k and x₂ = 0 (yielding a value of $10k). However, we have a more than just this constraint.
(2) Maximum mail for segment 1 constraint: x₁ ≤ 5000 (max. mail for segment 1), which is shaded in brown in the animation above.
We pick the highest value of x₁ possible, as we expect greater ROA for mail sent to segment 1. Hence, x₁ = 5000 in this case, and we move onto the next constraint. The new feasible region is the orange-brown area depicted above.
(3) Maximum mail for segment 2 constraint: x₂ ≤ 7500, shaded in green in the animation above.
This results in our final feasible region (the intersection of all three). From the previous step, we fix x₁ = 5000, and we evaluate along that vertical line. Some simple examples show that the optimal solution will always be at a corner point and not along the edge.
(4) Optimal solution: Because our final direct mail amount must be an integer for both variables, we pick the closest whole number to get the optimal solution:
- x₁ = 5000,
- x₂ = 5000, and
- Optimal total ROA of $9k.
Note that the solution is the same one found using the rank ordering algorithm, which leads us to the next question…
Why Should Lenders Care About Linear Programming to Optimize Direct Mail Allocation?
With LP, we can maximize metrics of interest (e.g., ROA, number of accounts, PV, etc.) and solve a problem limited by a feasible region and mathematically expressing all constraints, instead of taking care of one constraint at a time.
These are some of the advantages of using LP for these types of problems:
- LP seamlessly handles multiple constraints, even as the number of variables (i.e., segments) increases.
- We can add more constraints without affecting the complexity of the problem. For example, if the lender wanted to include loss rate or balance considerations, it would be easily added when using LP.
- By not manually picking which segments to prioritize, LP is more accurate and less error prone than rank ordering algorithms.
- LP is faster, as the algorithm finds the optimal solution by specifying the full feasible region from the start of the optimization.
- We have the flexibility to optimize different marketing channels by incorporating additional decision variables and constraints.
Do you have questions? We’d love to answer them!
Contact the authors by email at:
Interested in 2OS insights?
Check out the 2OS Insights page, where 2OS has shared industry insights through white papers, case studies, and more!
