Optimal advertising

Ad display

In this example we solve a simple optimal advertising problem in CVXPY. We have $m$ advertisers/ads, $i=1, \ldots, m$, and $n$ time slots, $t=1, \ldots, n$. $T_t$ is the total traffic in time slot $t$. $D_{it} \geq 0$ is the number of ad $i$ displayed in period $t$.

Our constraints are that $\sum_i D_{it} \leq T_t$ and that we satisfy our contracts for minimum total displays: $\sum_t D_{it} \geq c_i$. Our goal is to choose $D_{it}$.

Clicks and revenue

$C_{it}$ is the number of clicks on ad $i$ in period $t$. Our click model is $C_{it} = P_{it}D_{it}$, where $P_{it} \in [0,1]$ is the fraction of displays of ad $i$ in time $t$ that translate into clicks.

We are paid $R_i>0$ per click for ad $i$, up to a budget $B_i$. Our total ad revenue is thus

$$ S_i = \min \left\{ R_i \sum_t C_{it}, B_i\right\}, $$

a concave function of $D$.

Ad optimization

We choose the displays to maximize revenue, i.e., we solve the optimization problem

$$ \begin{array}{ll} \mbox{maximize} & \sum_i S_i \\ \mbox{subject to} & D \geq 0, \quad D^T{\bf 1} \leq T, \quad D {\bf 1} \geq c \end{array} $$

where the optimization variable is $D\in {\bf R}^{m \times n}$ and $T \in {\bf R}^n$, $c \in {\bf R}^m$, $R \in {\bf R}^m$, $B \in {\bf R}^m$, and $P \in {\bf R}^{m \times n}$ are problem data.

Example

In the following code we generate and solve an ad optimization problem with 24 hourly periods and 5 ads (A-E).

In [6]:
# Generate data for optimal advertising problem.
import numpy as np
np.random.seed(1)
m = 5
n = 24
SCALE = 10000
B = np.random.lognormal(mean=8, size=(m,1)) + 10000
B = 1000*np.round(B/1000)

P_ad = np.random.uniform(size=(m,1))
P_time = np.random.uniform(size=(1,n))
P = P_ad.dot(P_time)

T = np.sin(np.linspace(-2*np.pi/2,2*np.pi  -2*np.pi/2,n))*SCALE
T += -np.min(T) + SCALE
c = np.random.uniform(size=(m,1))
c *= 0.6*T.sum()/c.sum()
c = 1000*np.round(c/1000)
R = np.array([np.random.lognormal(c.min()/c[i]) for i in range(m)])
In [7]:
# Form and solve the optimal advertising problem.
from cvxpy import *
D = Variable((m,n))
Si = [min_elemwise(R[i]*P[i,:]*D[i,:].T, B[i]) for i in range(m)]
prob = Problem(Maximize(sum(Si)),
               [D >= 0,
                D.T*np.ones(m) <= T,
                D*np.ones(n) >= c])
prob.solve()
Out[7]:
42943.02650571528

We plot the total traffic $T$ below.

In [8]:
# Plot traffic.
import matplotlib.pyplot as plt
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
plt.plot(T)
plt.xlabel('Hour')
plt.ylabel("Traffic")
plt.show()

We plot the conversion fractions $P$ below.

In [9]:
# Plot P.
column_labels = range(0,24)
row_labels = list('ABCDE')
fig, ax = plt.subplots()
data = D.value.A
heatmap = ax.pcolor(P, cmap=plt.cm.Blues)

# put the major ticks at the middle of each cell
ax.set_xticks(np.arange(P.shape[1])+0.5, minor=False)
ax.set_yticks(np.arange(P.shape[0])+0.5, minor=False)

# want a more natural, table-like display
ax.invert_yaxis()
ax.xaxis.tick_top()

ax.set_xticklabels(column_labels, minor=False)
ax.set_yticklabels(row_labels, minor=False)
plt.show()

We plot the optimal displays $D$ below.

In [10]:
# Plot optimal D.
import matplotlib.pyplot as plt
%matplotlib inline
column_labels = range(0,24)
row_labels = list('ABCDE')
fig, ax = plt.subplots()
data = D.value.A
heatmap = ax.pcolor(data, cmap=plt.cm.Blues)

# put the major ticks at the middle of each cell
ax.set_xticks(np.arange(data.shape[1])+0.5, minor=False)
ax.set_yticks(np.arange(data.shape[0])+0.5, minor=False)

# want a more natural, table-like display
ax.invert_yaxis()
ax.xaxis.tick_top()

ax.set_xticklabels(column_labels, minor=False)
ax.set_yticklabels(row_labels, minor=False)
plt.show()