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.