MarketingDistillery.com is about web analytics, data science and marketing strategy

# Marketing Optimization with Linear Programming

(c) TomFishburne.com

CMOs need to make complex decisions about budget allocation and marketing investment. Deciding which campaigns will receive funding is never easy, especially with multiple factors and obligations that need to be taken into account. Agency and content preparation costs might be pre-set and an overall marketing strategy might require a certain share of voice or presence. At the same time, customers interact with multiple channels and not all overlapping marketing efforts will be fully incremental.

# Introduction to Linear Programming

There are multiple ways to perform Marketing Optimization and decide on investment allocation. Linear Programming is a well known methodology in the field of operational management. It was invented in 1939 and heavily utilized during the WWII for military logistics.

Linear Programming solves optimization problems under a set of linear constraints. Typical business uses involve work scheduling, inventory routing and workload assignments. In mathematical terms Linear Programming is expressed as:

• Maximize the objective function: $$c^Tx = \sum_i c_i x_i$$
• subject to a set of linear constraints: $$Ax \leq b$$
• and $$x_i \geq 0$$ for each $$i$$

The objective function is a simple linear combination and is therefore ideal for portfolio optimization problems. Variables $$c_i$$ can represent individual Returns-of-Investments (ROI) and $$x$$ would stand for the amount invested in each asset. The set of linear constraints is encoded as rows of the $$A$$ matrix.

Linear Programming is solved with the Simplex Algorithm. The set of constraints can be interpreted as hyper-planes in an n-dimensional space. These planes enclose a convex volume of space and the goal is to find a point within that volume which maximizes the objective function. The Simplex Algorithm is based on two observations:

1. The maximal point $$x$$ must lay on one of the vertices of the volume defined by the set of constraints.
2. If a given vertex is not maximal, there exists and edge from that vertex to another vertex with a higher value of the objective function.

To put it simply:

A region enclosed with hyperplanes defined by the constraint set. Vertices of this 3d solid/polytope marked in red will be investigated as possible solutions.

• The set of constraints (matrix $$A$$ and vector $$b$$) define faces of a high-dimensional “solid” and we are looking for a point $$x$$ inside that solid where the objective function is largest.
• The maximal point can only be at one of the vertices of the solid.
• We start with any vertex and move along the edges in the direction of a growing objective function.
• When we reach a vertex where all edges from that point lead to vertices with lower value of the objective function, the optimal solution was found.

The Simplex Algorithm has a very nice property – we only need to check a finite number of points at the vertices of the solid.

# Marketing Optimization example

Let us apply Linear Programming to a simple example in Marketing Optimization. We are to allocate funds to 4 marketing campaigns: a TV ad, SEO, Adwords and Facebook.

• ROI on each campaign is:
• 9% on TV
• 14% on SEO
• The total budget is £1,000,000.
• Search Engine Marketing (SEO + Adwords) is the primary focus and spend must exceed 60% of the total budget.
• Social media campaign on Facebook should cost no more than 20% of the budget.
• Production and airing of a TV ad will cost a minimum of £200,000.
• Minimal contract with a social agency for Facebook advertising is £80,000.
• An SEO content creation agency needs between £60,000 and £220,000.
• The marketing strategy says that Adwords cost should be no more 3 times the SEO costs.
• Channels have varying reach. It has been estimated using the number of customers you can reach by spending £1 in each channel:
• TV – 2.5 customers-per-pound
• SEO – 2.1 customers-per-pound
• The number of customers in the market base is estimated to be around 1.3 million people. You should allocate spend to match that number with campaign reach.

First of all, we encode channel ROI in the $$c^T$$ vector. Going forward, the order of channels in all vectors and matrix columns will be: TV, SEO, Adwords and Facebook.
$$c^T=(0.06,0.14,0.10,0.05)$$
Constraints need to be expressed in a common format as linear inequalities, i.e. for the j-th constraint:
$$a_{j1} x_1 + a_{j2} x_2 + a_{j3} x_3 + a_{j4} x_4 \leq b_j \enspace ,$$
For convenience, we will divide monetary values and customer counts by 1000.

## Constraint equations

Total budget:
$$x_1 + x_2 + x_3 + x_4 \leq 1000$$

SEO + Adwords must exceed 60%:
$$x_2 + x_3 \geq 0.6(x_1 + x_2 + x_3 + x_4) \\ \dots \\ 0.6 x_1 – 0.4 x_2 – 0.4 x_3 + 0.6 x_4 \leq 0$$

Facebook should not cost more than 20%:
$$x_4 \leq 0.2(x_1 + x_2 + x_3 + x_4) \\ \dots \\ -0.2 x_1 – 0.2 x_2 – 0.2 x_3 + 0.8 x_4 \leq 0$$
TV ad will cost a minimum of £200,000:
$$x_1 \geq 200 \\ \dots \\ -x_1 \leq -200$$
The minimal contract with the social agency:
$$-x_4 \leq -80$$
The minimal contract with the SEO agency:
$$-x_2 \leq -60$$
The maximal contract with the SEO agency:
$$x_2 \leq 220$$
Adwords no more than 3 times SEO costs:
$$3 x_2 \geq x_3 \\ \dots \\ -3 x_2 + x_3 \leq 0$$
Channels reach:
$$2.5 x_1 + 2.1 x_2 + 0.9 x_3 + 3.0 x_4 \leq 1300$$

We put all right-hand sides of the constraint inequalities into the vector $$b$$ and left-hand sides into the matrix $$A$$:
$$b = (1000, 0, 0, -200, -80, -60, 220, 0, 1300)$$

$$A = \left( \begin{array}{llll} 1 & 1 & 1 & 1 \\ 0.6 & -0.4 & -0.4 & 0.6 \\ -0.2 & -0.2 & -0.2 & 0.8\\ -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -3 & 1 & 0 \\ 2.5 & 2.1 & 0.9 & 3.0 \end{array} \right)$$

# Solving Linear Programming in R

There are multiple pieces of software that can solve Linear Programming problems. The GNU Linear Programming Kit is one, but R (as always) has a very elegant and easy to use package – linprog.

The above code produces the following (rather lengthy) output:

See the package documentation for details, but key pieces of information are:

1. The Objective function (Maximum) gives the maximum value of the objective function – the maximum total income from all campaigns is estimated to be around £73.3k (yes, I know this is small, but it is just an example).
2. The Solution section contains the optimal $$x$$. We should invest £200k in TV, £116k in SEO, £350k in Adwords and £80k in Facebook.
3. Constraints is a detailed diagnostic table where we can check if all constraints hold. The optimal investment sums up to approximately £746k so there is some budget left.

# Tips

• Always make sure you put all existing constraints into the model. Linear Programming has a tendency to pickup the campaign with the highest ROI and allocate all money into it.
• Try to identify constraints that affect all campaigns. Something similar to the “campaign reach” above.
• Follow a simple 4-step process:
1. Choose the unknowns. Usually, these will be investments or resource shares.
2. Write the objective function. What are you trying to maximize/minimize? Costs, margin, incremental value, time spent, reach etc.
3. Define all constraints in plain words and then transform them into a set of inequalities.
4. Plugin the data into your software of choice and solve.