8.4.6 R8. Google AdWords – Video 5: Solving the Problem

8.4.6 R8. Google AdWords – Video 5: Solving the Problem


Here, we have a
spreadsheet in LibreOffice that contains all of our data. Up here, we have the
basic data, which are the price-per-click
and click-through-rate. Below, we have the
average price per display, which we will actually be using. Below it, we have the
budgets, and below that we have the
query estimates. After the data, we then
have the variables. So these are the x_A1s through
x_A3s, the x_T1s through x_T3s and the x_V1s through x_V3s that
we saw in the previous video. And below those, we have the
objective, the constraints, so that the budgets
are not exceeded and that the query
estimates are not exceeded. So we’ll have to fill in all
of these expressions, which reflect, for example, how
many times query one is used in our advertising strategy,
how much of, for instance, T-Mobile’s budget we use in
your advertising strategy, as well as the objective, which
is the total average revenue from our advertising strategy. Let’s start by defining the
objective of our problem. To form the objective, we go
to the cell next to revenue, and we start by
writing,=SUMPRODUCT. The SUMPRODUCT function takes
two collections of cells, multiplies corresponding cells
together, and adds them up. Here we want to use SUMPRODUCT
to multiply the average prices per display with
the number of times we display each ad
with each query. Our variables are all the
cells between B35 and D37. And the average
price per display is contained in all the
cells between B17 and D19. So we need to input
these into the function. So we write B35:D37 comma,
so the comma indicates that we’re moving on to a
new collection of cells. Then we include B17:D19. We press Enter, and so now
we have our expression, which reflects the objective
value for our advertising strategy. Now to compute how much of
each advertiser’s budget we’re using, we’re going to use
the average price per display and the decision variables of
each individual advertiser. So to get, for example,
AT&T’s budget usage, we would use SUMPRODUCT
again in the same way that we used it
for the objective, but this time we
would use it just for AT&T’s decision variables
and AT&T’s average prices per display. So we use SUMPRODUCT
again, as I mentioned. So we write=SUMPRODUCT, but
this time we select the cells between B35 and D35. So we write B35:D35. These are the cells that
correspond to AT&T’s decision variables. For the second
collection of cells, we select the cells
between B17 and D17. These are the cells
that correspond to AT&T’s average
prices per display. We can do the same thing
for T-Mobile and Verizon. In this case, we don’t need to
enter the expressions again. We can just simply
drag these expressions, and LibreOffice
will conveniently fill the expressions in for us. And now we need to do a similar
thing for the number of times that we use each query. So, for example, to get the
number of times query one is used, we need
to add the cells corresponding to query one. In the spreadsheet, these
are the cells corresponding to B35 and B37. And in this case, we simply need
to add the decision variable cells — we don’t need to
multiply them with any other cells. So we just need to
use the sum function. So we write=SUM, and again,
we’re using the cell’s B35:B37. For query two, we
have to use SUM again. And we need to SUM the cells
corresponding to query two, so we write=SUM(C35:C37). And for query three, we
need to use SUM again, but this time we need to
use cells D35 through D37. So we write D35:D37. So we’ve now defined
all of the expressions that we’ll need for our model. Now we need to input
the decision variables, the objective, and
the constraints into the LibreOffice Solver. So we need to first open
up the LibreOffice Solver. So we go to Tools. We open up Tools, and
we click on Solver. So, to do this now, we
need to specify, again as I mentioned, all the
pieces of the problem. So for “Target cell” —
so the target cell here is the objective cell. So we need to specify
our objective. So this cell was just B40. And we want to maximize this
as we’re maximizing revenue. The “changing cells” here
are the decision variables. So this is just a collection
of cells, B35 through D37. So we write, B35:D37. Now, underneath, these
rows corresponding to the “Limiting
conditions”, these are just the constraints
of the problem. In the first row here, we’ll
handle the budget constraints. So under “Cell reference” we’ll
input the budget expression, and these are contained
in cells B45 through B47. So we can enter these or we can
just click on the input button and just select
them in this way. And then we click on
the shrink button here. Under “Operator”, we
want to select less than or equal to because we want to
ensure that the amount that we use of each budget is
less than the total budget of the advertiser. And here under
“Value”, we’re going to select the actual
budget amounts, which are on the right hand
side of these less than or equal to signs. So we select them,
and we put them in. So that handles the
budget constraints. And in the second
row here, we’re going to handle the query
estimate constraints. So here again, under
cell reference, we’re going to specify the
expressions that correspond to how much we use each query
in our advertising strategy. And so these are just the
cells, B50 through B52, which we select, and we
input them into the solver. Under operator, we want
to keep it as less than or equal to, because we want to
ensure that the amount that we use each query is less than or
equal to the expected number of times that we
estimate for that query. And under value, we want to
input the query estimates, which are just the
cells, D50 through D52. So, we can just select them
in this way, and input them. So, at this point, it
might be tempting to think that we are done, but we have
two more things we need to do. First, we need to
tell the solver to explicitly treat this as a
linear optimization problem. Second, we need to include
another set of constraints. This set of constraints
requires each decision variable to be greater than
or equal to zero, since it does not
make sense to display an advertiser with a certain
query some negative number of times. Now, while we could include
these constraints here, these types of constraints are
very common and very typical in linear optimization models. They come up all the time. And, in fact, they
come up so often, that solvers often have an
option that you can toggle, that incorporates these
constraints automatically. So to handle both of
these considerations. Let’s just click on Options. And under options, where
we have the drop down menu for “Solver engine”,
we’ll click on there, and then we’ll select
LibreOffice Linear Solver. This indicates to LibreOffice
to use the linear optimization solver for this problem. And under the settings
here, one of the settings, is to assume that the
variables are non-negative. We’ll just activate
that option and hit OK. And now we’re ready
to solve the problem. So if we hit solve, we
get this dialogue that says that solving
successfully finished, and that our result,
in this case, this is the objective
function, was 428. So we have an
advertising strategy that achieves an
average revenue of $428. Let’s just hit here, Keep
Result, and just take a look. The cells that we specified
as the decision variables have been populated with
their optimal values. So our optimal strategy, based
on this linear optimization solution is the
following: so we’re going to show AT&T with
query one 40 times; we’re going to show AT&T
with query two also 40 times; we’re going to show AT&T
with query three 80 times; for T-Mobile, we’ll show
T-Mobile’s ad with query one 100 times; and we’re only
going to show Verizon’s ad with query two, and we’re
going to show it 40 times. So this specifies, completely,
the advertising strategy that Google should use. And this strategy,
as we just saw, achieves an average
revenue of $428. Let’s double check
that the solution is feasible by looking at
the budgets and the query estimates. So if we scroll
down here, we see that AT&T’s budget that
we use here is $168. AT&T’s actual budget is $170. We can see that for the
other two advertisers, that we are in the
clear for both of them. Similarly, with
the query estimates we can see that
for all the queries that we are considering
here, we do not use any query more
than the estimate for the number of times that
we expect to see that query. And finally, as one last check,
all the decision variable values that we see here are all
greater than or equal to zero. So we’re not using
any advertiser with any query a negative
number times, which obviously would not make sense. So, the solution as a whole
is a feasible solution. In the next video,
we’ll show how to solve the problem using
a greedy common sense approach, where we will allocate
ads to queries by prioritizing them by their average
price per display.

Leave a Reply

Your email address will not be published. Required fields are marked *