Optimal advertising
This example is taken from https://web.stanford.edu/~boyd/papers/pdf/cvx_applications.pdf.
Setup:
- We have $m$ adverts and $n$ time slots
- The total traffic in time slot $t$ is $T_t$
- The number of ad $i$ displayed in period $t$ is $D_{it} \geq 0$
- We require $\sum_{i=1}^m D_{it} \leq T_t$ since we cannot show more than $T_t$ ads during time slot $t$.
- We require $\sum_{t=1}^n D_{it} \geq c_i$ to fulfill a contract to show advertisement $i$ at least $c_i$ times.
Goal: choose $D_{it}$.
For some empirical $P_{it}$ with $0 \leq P_{it} \leq 1$, we obtain $C_{it} = P_{it}D_{it}$ clicks for ad $i$, which pays us some number $R_i > 0$ up to a budget $B_i$. The ad revenue for ad $i$ is $S_i = \min( R_i \sum_t C_{it}, B_i )$ which is concave in $D$. We aim to maximize $\sum_i S_i$.
using Random
using Distributions: LogNormal
Random.seed!(1);
m = 5; # number of adverts
n = 24; # number of time slots
SCALE = 10000;
B = rand(LogNormal(8), m) .+ 10000;
B = round.(B, digits = 3); # Budget
P_ad = rand(m);
P_time = rand(1, n);
P = P_ad * P_time;
T = sin.(range(-2 * pi / 2, stop = 2 * pi - 2 * pi / 2, length = n)) * SCALE;
T .+= -minimum(T) + SCALE; # traffic
c = rand(m); # contractual minimum
c *= 0.6 * sum(T) / sum(c);
c = round.(c, digits = 3);
R = [rand(LogNormal(minimum(c) / c[i]), 1) for i in 1:m]; # revenue
# Form and solve the optimal advertising problem.
using Convex, SCS;
D = Variable(m, n);
Si = [min(R[i] * dot(P[i, :], D[i, :]'), B[i]) for i in 1:m];
problem =
maximize(sum(Si), [D >= 0, sum(D, dims = 1)' <= T, sum(D, dims = 2) >= c]);
solve!(problem, SCS.Optimizer; silent = true)
Problem statistics
problem is DCP : true
number of variables : 1 (120 scalar elements)
number of constraints : 3 (149 scalar elements)
number of coefficients : 453
number of atoms : 51
Solution summary
termination status : OPTIMAL
primal status : FEASIBLE_POINT
dual status : FEASIBLE_POINT
objective value : 103522.3866
Expression graph
maximize
└─ + (concave; real)
├─ min (concave; real)
│ ├─ * (affine; real)
│ │ ├─ …
│ │ └─ …
│ └─ [12777.8;;]
├─ min (concave; real)
│ ├─ * (affine; real)
│ │ ├─ …
│ │ └─ …
│ └─ [15071.9;;]
├─ min (concave; real)
│ ├─ * (affine; real)
│ │ ├─ …
│ │ └─ …
│ └─ [11330.3;;]
⋮
subject to
├─ ≥ constraint (affine)
│ └─ + (affine; real)
│ ├─ 5×24 real variable (id: 373…752)
│ └─ Convex.NegateAtom (constant; negative)
│ └─ …
├─ ≤ constraint (affine)
│ └─ + (affine; real)
│ ├─ reshape (affine; real)
│ │ └─ …
│ └─ 24×1 Matrix{Float64}
└─ ≥ constraint (affine)
└─ + (affine; real)
├─ * (affine; real)
│ ├─ …
│ └─ …
└─ 5×1 Matrix{Float64}
Plot traffic.
using Plots
plot(1:length(T), T, xlabel = "hour", ylabel = "Traffic")
Plot P.
heatmap(P)
Plot optimal D.
heatmap(evaluate(D))
This page was generated using Literate.jl.