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{split} \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} \end{split}\]

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).

# 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,))
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)])

# Form and solve the optimal advertising problem.
import cvxpy as cp

D = cp.Variable((m, n))
Si = [cp.minimum(R[i] * P[i, :] @ D[i, :].T, B[i]) for i in range(m)]
prob = cp.Problem(
    cp.Maximize(cp.sum(Si)), [D >= 0, D.T @ np.ones(m) <= T, D @ np.ones(n) >= c]
)
prob.solve()

/opt/hostedtoolcache/Python/3.10.12/x64/lib/python3.10/site-packages/cvxpy/problems/problem.py:1387: UserWarning: Solution may be inaccurate. Try another solver, adjusting the solver settings, or solve with verbose=True for more information.
  warnings.warn(

42942.60448618613

We plot the total traffic \(T\) below.

# Plot traffic.
import matplotlib.pyplot as plt

%config InlineBackend.figure_format = 'svg'
plt.plot(T)
plt.xlabel("Hour")
plt.ylabel("Traffic")
plt.show()

We plot the conversion fractions \(P\) below.

# Plot P.
column_labels = range(0, 24)
row_labels = list("ABCDE")
fig, ax = plt.subplots()
data = D.value
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.

# Plot optimal D.
import matplotlib.pyplot as plt

column_labels = range(0, 24)
row_labels = list("ABCDE")
fig, ax = plt.subplots()
data = D.value
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()