A multiobjective approach for maximizing the reach or GRP of different brands in TV advertising

• Published date: 01 May 2020
• DOI: http://doi.org/10.1111/itor.12481
• Author: Rommel G. Regis,Vivian M. Evangelista
• Date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1664–1698

DOI: 10.1111/itor.12481

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A multiobjective approach for maximizing the reach or GRP of

different brands in TV advertising

Vivian M. Evangelistaaand Rommel G. Regisb

aDepartment of Decision and System Sciences, Saint Joseph’s University, 5600 City Avenue,P hiladelphia, PA 19131, USA

bDepartment of Mathematics, Saint Joseph’s University, 5600 City Avenue, Philadelphia, PA19131, USA

E-mail: vevangel@sju.edu [Evangelista];rregis@sju.edu [Regis]

Received 3 October 2016; receivedin revised form 14 August 2017; accepted 10 October 2017

Abstract

This paper focuses on a multiobjective optimization problem in TV advertising from an advertising agency’s

perspective, which involves deciding on which commercial breaks to air the ads of various brands to jointly

maximize reach or gross rating point (GRP) for the different brands subject to budget constraints, brand

competition constraints, and other scheduling constraints. We present a multiobjective integer programming

formulation of this problem and develop and implement algorithms for generating provably Pareto-optimal

solutions. We also develop reductionand visualization procedures to aid a decision maker in choosing suitable

subsets of the Pareto-optimal solutions obtained. Numerical experiments on five TV advertising problems

involving 20–40 objective functions and thousands of decision variables and constraints demonstrate the

effectivenessof the proposed formulation and solution methods in generating Pareto-optimalobjective vectors

that reflect brand priorities and that are well distributedalong the Pareto front.

Keywords:Optimal advertising; multiobjective optimization; Pareto-optimal; reach; gross rating point; integer program-

ming

1. Introduction

This paper presents an optimization problem in TV advertising, specifically in the area of media

planning. Media planning for TV involves scheduling ads on various TV shows in orderto maximiz e

viewership forthe ads subject to budget and other constraints (Fleming and Pashkevich, 2007). Since

companies spend large amounts of money on TV advertising, it is important to optimize the media

planning process.

Fleming and Pashkevich (2007) note that the key players in the media planning process are the

company, the advertising agency, and the TV network. They describe the media planning process

as follows. Companies typically hire advertising agencies to perform media planning functions for

them, with the company setting a fixed advertising budget. The ad agency takes charge of buying

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

V.M. Evangelista and R. G. Regis / Intl. Trans. in Op. Res. 27 (2020) 1664–1698 1665

advertising time for multiple brands from the TV networks. The ad agency then creates an optimal

schedule of ads, selecting which shows and commercial breaks to air the ads in as well as how often

to air these ads. The main goal is to maximize viewership for the multiple brands (Fleming and

Pashkevich, 2007).

Optimization problems in TV advertising may be formulated from the company’s point of view,

the advertising agency, or the TV network. A classic linear programming formulation of the media

planning problem from the the company’s perspective is described in Brown and Warshaw (1965),

which involves various media not just TV. Bhattacharya (2009) provides a more recent formula-

tion to maximize reach in TV and newspaper advertising from a company’s point of view that

involves stochastic goal programming. Next, there has been some work on scheduling ads from

the perspective of the TV networks. For example, Bollapragada and Garbiras (2004) formulate the

ad scheduling problem as an integer program where the objective is to minimize the total penalty

incurred in not meeting requirements such as ensuring that no two competing products air in the

same commercial break. More recently, Lupo (2015) developed a multiobjective approach for TV

scheduling from the the TV network’s point of view where total ratings and total costs are the

objectives to optimize.

There has also been some work on media planning from the advertising agency’s perspective.

For example, Mihiotis and Tsakiris (2004) focus on optimally scheduling an ad within TV shows

in order to maximize viewership for the ad. They describe media planning from the advertising

agency’s perspective but for a single product only. Fleming and Pashkevich (2007) also focus on a

media planning problem from the perspective of the advertising agency. Their formulation involves

deciding on which commercial breaks to air the ads of various brands in order to jointly maximize

reach or gross rating point (GRP) for the different brands subject to budget constraints, brand

competition constraints, and other scheduling constraints. Garc´

ıa-Villoria and Salhi (2015) incor-

porated audience rating requests in a single-objective formulation of the TV scheduling problem.

In their formulation, each break has an associated audience rating: high, medium, or low. Then,

the advertiser (or advertising agency) requests a minimum number of times to run a commercial

on breaks with high or medium (or higher) audience ratings. In addition, they also incorporated

airing regularity requirements, meaning that multiple airings of the same commercial should be as

evenly spaced as possible within a specified time horizon. Moreover, Makaji´

c-Nikoli´

c et al. (2011)

developed a single-objective binary integer programming (IP) formulation to maximize targetrating

points (TRPs) subject to constraints on daily TRP, number of commercials, available budget, and

desired reach. In addition, Stanojevi´

c et al. (2011) developed a goal programming approach to

model several goals for media planning with the primary goal being to provide the proper number

of exposures of a TV commercial to as many target viewers as possible, subject to constraints on

budget and daily ratings.

With the advances in digital TV and mobile TV viewing on various mobile devices, it has become

easier to assign targeted personalized ads to individual viewers (Bozios et al., 2001). Adany et al.

(2013) presented IP models and several heuristics for the targeted advertising problem, which

involves assigning ads to individual viewers who belong to the ad’s target population with the

goal of maximizing total revenue. Moreover, there are personalized advertisementrecommendation

systems based on user preference and social network information (Ha et al., 2015).

This paper has three main goals. First, it reviews the discrete nonlinear formulation of the

multiobjective optimal advertising problem by Fleming and Pashkevich (2007) and presents an

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

1666 V.M. Evangelista and R. G. Regis / Intl. Trans. in Op. Res. 27 (2020) 1664–1698

alternative integer linear programming formulation for this problem. Our formulation models

the same requirements as in Fleming and Pashkevich (2007), but it is simpler because all the

constraints are linear.Second, this paper develops an exact algorithm that can be proved to generate

Pareto-optimal solutions for this multiobjective advertising problembased on our new optimization

formulation. In contrast, Fleming and Pashkevich (2007) used a multiobjective genetic algorithm

augmented by a local optimization routine, which is a heuristic with no guarantee of producing

solutions that are truly Pareto-optimal. Our algorithm wastested on five TV advertising scheduling

examples involving 20–40 objectives and thousands of decision variables and constraints, and

since the formulation involves binary decision variables, the scalability of the method to much

larger problems needs further study. However, our new multiobjective IP (MOIP) formulation can

potentially be used to design more effective heuristics for the problem, possibly with provable

approximationguarantees. Finally, this paper provides a procedure for reducing and visualizing the

set of Pareto-optimal solutions obtained when the problemhas a large number of objective functions

and decision variables. Yepes et al. (2015) use a cognitive approach for analyzing and reducing the

Pareto-optimal set for multiobjective optimization of structural problems. This approach improved

knowledge of the decision-making process and allowed decision makers to be involved and learn

from the process (Yepes et al., 2015). Not much attention has been paid to procedures that can

aid the decision maker in choosing Pareto-optimal solution(s) in this situation so our proposed

procedure can be used for multiobjective problems with many objectives in other disciplines.

This paper is organized as follows. Section 2 defines some basic advertising terms while Section 3

presents some preliminaries on multiobjective optimization. Section 4 presents the optimization

formulation of the TV advertising scheduling problem by Fleming and Pashkevich (2007) and

our proposed MOIP formulation. Section 5 develops our proposed method for solving the TV

advertising scheduling problem using our MOIP formulation. Next, Section 6 provides numerical

results for five TV advertising scheduling problems. Finally, Section 7 provides a summary and

some conclusions. A preliminary version of the work in this paper was presented at the CORS 58th

Annual Conference (Regis and Evangelista, 2016).

2. Basic marketing and advertising terms

Here are some definitions of the marketing terms that will be used in this paper. There are some

slight differences in how these terms are defined in various sources. However, for consistency and

precision in the mathematical formulations, we will sometimes deviate slightly from their standard

definitions in marketing textbooks.

Target market: The target market of a product or brand is the consumer demographic that the

product or brand is intended for (Solomon et al., 2012). Example: females, age 18 and above.

Reach: The reachofanadonaparticularTVshowis the percentage of the target market that will

be exposed to the ad at least once when it is aired on that TV show (Solomon et al., 2012).

In some cases, it would be helpful to refer to the reach of a TV show for a particular consumer

demographic (e.g., females, age 18 and above) as the percentage of this demographic that watches

this TV show. If this consumer demographic is the target market for Brand A, then the reach of

the TV show for this demographic is also the reach of an ad for Brand A on this TV show. When the

consumer demographic is understood from the context, we simply refer to the reach of a TV s how.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies