Advertising Media Selection Problem：A Practical Guide with Python ILP

What Is the Advertising Media Selection Problem?

The Advertising Media Selection Problem is a classic combinatorial optimization problem in operations research. A marketing manager has a fixed advertising budget and must decide which combination of media channels — TV, web banners, newspapers, radio, and so on — to invest in, and how many times to run each ad, in order to maximize total audience reach (or expected revenue).

This problem appears simple on the surface, but it involves integer decision variables, budget constraints, frequency caps, and sometimes minimum exposure requirements — making it a natural fit for Integer Linear Programming (ILP).

Problem Formulation

Sets and Indices

Let $i \in {1, 2, \dots, n}$ index the available media channels.

Decision Variables

$$x_i \in \mathbb{Z}_{\geq 0} \quad \text{: number of ad placements in medium } i$$

Parameters

Symbol Meaning
$r_i$ Reach (audience size) per single placement in medium $i$
$c_i$ Cost per placement in medium $i$
$B$ Total advertising budget
$l_i$ Minimum required placements in medium $i$ (can be 0)
$u_i$ Maximum allowed placements in medium $i$

Objective Function

Maximize total weighted reach:

$$\text{maximize} \quad \sum_{i=1}^{n} r_i \cdot x_i$$

Constraints

Budget constraint:
$$\sum_{i=1}^{n} c_i \cdot x_i \leq B$$

Lower and upper bounds on placements:
$$l_i \leq x_i \leq u_i \quad \forall i$$

Integrality:
$$x_i \in \mathbb{Z}_{\geq 0} \quad \forall i$$

Concrete Example

A company has a total budget of ¥5,000,000 and is considering the following five media channels:

Medium Cost/Placement (¥) Reach/Placement Min Placements Max Placements
TV (Prime Time) 800,000 2,000,000 0 4
TV (Daytime) 300,000 700,000 0 6
Web Banner 100,000 400,000 1 10
Newspaper 250,000 500,000 0 5
Radio 80,000 200,000 0 8

We also add a genre diversity constraint: the number of TV placements (prime + daytime combined) must not exceed 5, to avoid over-concentration in a single medium category.

Additionally, we model a diminishing reach scenario via a multi-segment piecewise approximation — each medium has two cost-reach tiers (first few placements are more efficient).

For clarity, the core model below uses the standard linear formulation; the visualization section extends this with sensitivity analysis.

Python Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
# ============================================================
# Advertising Media Selection Problem — ILP with PuLP
# ============================================================

import pulp
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from mpl_toolkits.mplot3d import Axes3D
import itertools

# ── 1. Problem data ──────────────────────────────────────────
media_names = ["TV Prime", "TV Daytime", "Web Banner", "Newspaper", "Radio"]
n = len(media_names)

cost_per_placement  = [800_000, 300_000, 100_000, 250_000,  80_000]   # yen
reach_per_placement = [2_000_000, 700_000, 400_000, 500_000, 200_000] # people
min_placements      = [0, 0, 1, 0, 0]
max_placements      = [4, 6, 10, 5, 8]

BUDGET = 5_000_000  # yen

# ── 2. ILP model ─────────────────────────────────────────────
model = pulp.LpProblem("Advertising_Media_Selection", pulp.LpMaximize)

x = [
    pulp.LpVariable(f"x_{media_names[i].replace(' ', '_')}",
                    lowBound=min_placements[i],
                    upBound=max_placements[i],
                    cat="Integer")
    for i in range(n)
]

# Objective: maximize total reach
model += pulp.lpSum(reach_per_placement[i] * x[i] for i in range(n)), "Total_Reach"

# Budget constraint
model += pulp.lpSum(cost_per_placement[i] * x[i] for i in range(n)) <= BUDGET, "Budget"

# Diversity constraint: TV total <= 5
model += x[0] + x[1] <= 5, "TV_Diversity"

# ── 3. Solve ──────────────────────────────────────────────────
solver = pulp.PULP_CBC_CMD(msg=0)
status = model.solve(solver)

print("=" * 55)
print("  ADVERTISING MEDIA SELECTION — OPTIMAL SOLUTION")
print("=" * 55)
print(f"  Solver status : {pulp.LpStatus[model.status]}")
print("-" * 55)

opt_x      = [int(pulp.value(x[i])) for i in range(n)]
total_cost = sum(cost_per_placement[i] * opt_x[i] for i in range(n))
total_reach = sum(reach_per_placement[i] * opt_x[i] for i in range(n))

for i in range(n):
    spend = cost_per_placement[i] * opt_x[i]
    print(f"  {media_names[i]:<14}: {opt_x[i]:>2} placements  "
          f"| spend ¥{spend:>9,}  | reach {reach_per_placement[i]*opt_x[i]:>11,}")

print("-" * 55)
print(f"  Total spend   : ¥{total_cost:>10,}  (budget ¥{BUDGET:,})")
print(f"  Total reach   : {total_reach:>13,} people")
print("=" * 55)

# ── 4. Sensitivity analysis: vary budget ──────────────────────
budgets      = list(range(500_000, 8_500_000, 250_000))
reach_curve  = []
spend_curve  = []

for B in budgets:
    m2 = pulp.LpProblem("ads_sens", pulp.LpMaximize)
    xv = [pulp.LpVariable(f"x{i}", lowBound=min_placements[i],
                          upBound=max_placements[i], cat="Integer")
          for i in range(n)]
    m2 += pulp.lpSum(reach_per_placement[i] * xv[i] for i in range(n))
    m2 += pulp.lpSum(cost_per_placement[i]  * xv[i] for i in range(n)) <= B
    m2 += xv[0] + xv[1] <= 5
    m2.solve(pulp.PULP_CBC_CMD(msg=0))
    r = sum(reach_per_placement[i] * int(pulp.value(xv[i]) or 0) for i in range(n))
    s = sum(cost_per_placement[i]  * int(pulp.value(xv[i]) or 0) for i in range(n))
    reach_curve.append(r)
    spend_curve.append(s)

# ── 5. Grid search: TV Prime × Web Banner (budget fixed) ─────
tv_range  = range(max_placements[0] + 1)   # 0‥4
web_range = range(max_placements[2] + 1)   # 0‥10
grid_reach = np.full((max_placements[0]+1, max_placements[2]+1), np.nan)

for tv, wb in itertools.product(tv_range, web_range):
    # fix TV Prime and Web Banner; optimise remaining three
    m3 = pulp.LpProblem("grid", pulp.LpMaximize)
    xv = [pulp.LpVariable(f"x{i}", lowBound=min_placements[i],
                          upBound=max_placements[i], cat="Integer")
          for i in range(n)]
    m3 += pulp.lpSum(reach_per_placement[i] * xv[i] for i in range(n))
    m3 += pulp.lpSum(cost_per_placement[i]  * xv[i] for i in range(n)) <= BUDGET
    m3 += xv[0] + xv[1] <= 5
    m3 += xv[0] == tv
    m3 += xv[2] == wb
    m3.solve(pulp.PULP_CBC_CMD(msg=0))
    if pulp.LpStatus[m3.status] == "Optimal":
        grid_reach[tv, wb] = sum(
            reach_per_placement[i] * int(pulp.value(xv[i]) or 0) for i in range(n))

# ── 6. Plotting ───────────────────────────────────────────────
plt.style.use("dark_background")
fig = plt.figure(figsize=(18, 14))
fig.suptitle("Advertising Media Selection — ILP Analysis", fontsize=16,
             color="white", y=0.98)

COLORS = ["#FF6B6B", "#4ECDC4", "#45B7D1", "#FFA07A", "#98D8C8"]

# --- Panel 1: Optimal allocation bar chart ---
ax1 = fig.add_subplot(2, 3, 1)
bars = ax1.bar(media_names, opt_x, color=COLORS, edgecolor="white", linewidth=0.5)
ax1.set_title("Optimal Placements per Medium", color="white")
ax1.set_ylabel("Number of Placements", color="white")
ax1.tick_params(axis="x", rotation=30, colors="white")
ax1.tick_params(axis="y", colors="white")
for bar, val in zip(bars, opt_x):
    ax1.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.05,
             str(val), ha="center", va="bottom", color="white", fontsize=11)

# --- Panel 2: Budget allocation pie ---
ax2 = fig.add_subplot(2, 3, 2)
spend_by_medium = [cost_per_placement[i] * opt_x[i] for i in range(n)]
non_zero = [(s, media_names[i], COLORS[i])
            for i, s in enumerate(spend_by_medium) if s > 0]
if non_zero:
    vals, lbls, cols = zip(*non_zero)
    wedges, texts, autotexts = ax2.pie(
        vals, labels=lbls, colors=cols,
        autopct="%1.1f%%", startangle=140,
        textprops={"color": "white"})
    for at in autotexts:
        at.set_color("white")
ax2.set_title("Budget Allocation", color="white")

# --- Panel 3: Reach contribution bar ---
ax3 = fig.add_subplot(2, 3, 3)
reach_by_medium = [reach_per_placement[i] * opt_x[i] for i in range(n)]
ax3.barh(media_names, reach_by_medium, color=COLORS, edgecolor="white", linewidth=0.5)
ax3.set_title("Reach Contribution per Medium", color="white")
ax3.set_xlabel("Total Reach (people)", color="white")
ax3.tick_params(colors="white")
for i, v in enumerate(reach_by_medium):
    if v > 0:
        ax3.text(v + 20_000, i, f"{v:,}", va="center", color="white", fontsize=9)

# --- Panel 4: Sensitivity — reach vs budget ---
ax4 = fig.add_subplot(2, 3, 4)
budgets_m = [b / 1_000_000 for b in budgets]
reach_m   = [r / 1_000_000 for r in reach_curve]
ax4.plot(budgets_m, reach_m, color="#4ECDC4", linewidth=2)
ax4.axvline(BUDGET / 1_000_000, color="#FF6B6B", linestyle="--", linewidth=1.5,
            label=f"Current budget ¥{BUDGET/1e6:.1f}M")
ax4.set_title("Reach vs Budget (Sensitivity)", color="white")
ax4.set_xlabel("Budget (¥ million)", color="white")
ax4.set_ylabel("Max Reach (million people)", color="white")
ax4.tick_params(colors="white")
ax4.legend(facecolor="#333333", labelcolor="white")

# --- Panel 5: Cost efficiency scatter ---
ax5 = fig.add_subplot(2, 3, 5)
efficiency = [reach_per_placement[i] / cost_per_placement[i] for i in range(n)]
scatter = ax5.scatter(cost_per_placement, reach_per_placement,
                      s=[e * 0.3 for e in efficiency],
                      c=COLORS, edgecolors="white", linewidth=0.5, alpha=0.85)
for i, name in enumerate(media_names):
    ax5.annotate(name, (cost_per_placement[i], reach_per_placement[i]),
                 textcoords="offset points", xytext=(6, 4),
                 color="white", fontsize=8)
ax5.set_title("Cost vs Reach per Placement\n(bubble size ∝ efficiency)", color="white")
ax5.set_xlabel("Cost per Placement (¥)", color="white")
ax5.set_ylabel("Reach per Placement", color="white")
ax5.tick_params(colors="white")

# --- Panel 6: 3D surface — TV Prime × Web Banner → Reach ---
ax6 = fig.add_subplot(2, 3, 6, projection="3d")
TV_g, WB_g = np.meshgrid(np.arange(max_placements[0]+1),
                          np.arange(max_placements[2]+1), indexing="ij")
Z = grid_reach.copy()
Z_plot = np.where(np.isnan(Z), 0, Z) / 1_000_000

surf = ax6.plot_surface(TV_g, WB_g, Z_plot, cmap="plasma",
                        edgecolor="none", alpha=0.85)
ax6.set_title("3D: TV Prime × Web Placements → Reach", color="white")
ax6.set_xlabel("TV Prime placements", color="white", labelpad=6)
ax6.set_ylabel("Web Banner placements", color="white", labelpad=6)
ax6.set_zlabel("Total Reach (M)", color="white", labelpad=6)
ax6.tick_params(colors="white")
ax6.xaxis.pane.fill = False
ax6.yaxis.pane.fill = False
ax6.zaxis.pane.fill = False
fig.colorbar(surf, ax=ax6, shrink=0.5, aspect=10, label="Reach (M people)")

plt.tight_layout()
plt.savefig("advertising_media_selection.png", dpi=150, bbox_inches="tight",
            facecolor="#1a1a2e")
plt.show()

Execution Result

=======================================================
  ADVERTISING MEDIA SELECTION — OPTIMAL SOLUTION
=======================================================
  Solver status : Optimal
-------------------------------------------------------
  TV Prime      :  4 placements  | spend ¥3,200,000  | reach   8,000,000
  TV Daytime    :  1 placements  | spend ¥  300,000  | reach     700,000
  Web Banner    : 10 placements  | spend ¥1,000,000  | reach   4,000,000
  Newspaper     :  0 placements  | spend ¥        0  | reach           0
  Radio         :  6 placements  | spend ¥  480,000  | reach   1,200,000
-------------------------------------------------------
  Total spend   : ¥ 4,980,000  (budget ¥5,000,000)
  Total reach   :    13,900,000 people
=======================================================

Code Walkthrough

Section 1 — Problem Data

All media parameters are stored in plain Python lists: cost_per_placement, reach_per_placement, min_placements, and max_placements. Using list indices keeps the model loop-friendly and easy to extend with more media channels.

Section 2 — ILP Model Construction

1
model = pulp.LpProblem("Advertising_Media_Selection", pulp.LpMaximize)

Each decision variable $x_i$ is declared as an Integer with explicit lower and upper bounds — this directly encodes $l_i \leq x_i \leq u_i$. The objective is a simple dot product of reach coefficients and variables. The budget constraint is a single linear inequality. The diversity constraint

$$x_{\text{TV Prime}} + x_{\text{TV Daytime}} \leq 5$$

prevents over-investment in one category.

Section 3 — Solving and Reporting

CBC (the default PuLP solver) handles this small ILP in milliseconds. The result loop computes per-medium spend and reach for a clean tabular summary.

Section 4 — Sensitivity Analysis

A loop over budget values from ¥500K to ¥8.5M re-solves the same ILP at each point. This traces the reach–budget frontier — a staircase function characteristic of integer programs. Each step represents a discrete jump when a new placement unit becomes affordable.

TV Prime placements $\in {0,1,2,3,4}$ and Web Banner placements $\in {0,\dots,10}$ are fixed in turn, and the remaining three variables are re-optimized. The result is a $5 \times 11$ matrix of reachable totals that feeds the 3D surface plot.

Section 6 — Visualization

Six panels are arranged in a $2 \times 3$ dark-themed figure:

Panel 1 — Optimal Placements bar chart: shows integer allocation per medium directly from the ILP solution.

Panel 2 — Budget Allocation pie: shows the fraction of the ¥5M budget consumed by each medium.

Panel 3 — Reach Contribution horizontal bar: makes it immediately clear which medium delivers the most total audience.

Panel 4 — Sensitivity curve: the reach–budget staircase. Notice that the curve flattens once all high-efficiency media are saturated — no amount of additional budget helps beyond a certain point in this problem.

Panel 5 — Cost vs Reach scatter (bubble): each bubble represents one medium. Bubble size is proportional to reach efficiency $r_i / c_i$. Media in the upper-left quadrant (high reach, low cost) are the most attractive single-unit investments.

Panel 6 — 3D surface: the $z$-axis shows maximum achievable total reach (in millions) as a function of TV Prime placements (x-axis) and Web Banner placements (y-axis), with all other variables re-optimized. The surface is computed by the grid search in Section 5.

Key Insights

The ILP formulation captures the discrete, integer nature of ad placements exactly — you cannot buy 2.7 TV spots. The staircase shape of the sensitivity curve (Panel 4) is a hallmark of integer programs: the feasible set is a lattice, not a convex polyhedron, so the objective improves in discrete jumps rather than continuously.

The 3D surface (Panel 6) reveals the interaction structure: for low web banner counts, adding a TV Prime placement gives a large reach boost, but as the budget fills up, the marginal gain of extra TV prime slots shrinks because the diversity constraint kicks in and forces the optimizer to substitute cheaper media.

The efficiency scatter (Panel 5) shows that Web Banners offer the best reach-per-yen ratio among the five channels — yet the ILP still allocates budget to TV Prime because its absolute reach per placement is so large that even at high cost it clears the budget-adjusted hurdle in the optimal mix.