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: 904…137)
   │     └─ 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.