Backpack problem in contextual advertising for message boards

I want to describe here a case with one of the best (in my opinion) ways to manage daily budget limits for contextual advertising campaigns. It seems to me that such a scheme may be suitable for companies with indirect monetization of traffic, for example, for classifieds, in auto, real estate and everything in the world. Perhaps not only for them.



This is my first experience of writing public articles (but my second attempt), so sorry if something goes wrong. I would be glad to have constructive comments.

Why not direct monetization?

Because companies whose monetization is direct and the ROI is calculated well enough can afford to invest in an advertising source to the limit of its capacity, as long as the investment pays off. On the other hand, sites like message boards often cannot afford it. Because do not have a rigid connection with the return on investment, because do not sell goods and services themselves, but work according to an advertising model. Simply put: today you can spend a lot of money in context, but tomorrow this will not result in more advertising contracts on the classified site.



Therefore, for such sites, the traffic attracted from contextual advertising is monetized indirectly, with a time delay, and only part of the traffic has direct monetization, for example, in calls.





For the purposes of this essay, let's assume that we already have a media plan with a budget for the next month and working ad accounts. What's next?

What do these companies' ad accounts usually look like?

1. Most likely there will be at least two advertising accounts. Yandex Direct and Google Ads, and in this regard, we are very lucky, because competition is always better than its absence, and this is an excellent field for healthy optimization
2. It is possible that there will be even more advertising accounts, for example, due to the fact that the campaigns for conversion, project, support team, or on another basis are divided for different accounts
3. Each ad account will contain a set of advertising campaigns (AC), let's say their names will indicate some way of classifying campaigns (for example, by region, by project, by type of placement, by platform)

In general, it is completely normal for a situation when the number of all advertising campaigns is quite large, say, about several thousand. Of course, they are somehow clustered and, as a rule, there is logic there, according to which you can select one or another subset of campaigns in order to view statistics or revise the settings, or make a massive change.





With such a large set of ACs, it is quite difficult to calculate and assign daily budgets manually. We will now describe the automation of this process.

Let's take a look at the media plan for the next month

Let's call a media plan node a combination of all classification signs for which the budget for the next month is set. Let's say you have defined (region, product, and type of deal, say lease or sale) and a budget.



Most likely, the site in the MT will be set not only a budget, but also targets for the cost of conversion. Let me make, in my opinion, an important remark:

For assigning daily budgets and hitting the MT on a budget, cost per conversion targets are completely irrelevant. So we just don't look at them now.

Formulation of the problem

You never know what happens in this world, almost certainly I am sure of the following statement:

The number of media plan nodes will always be less than or equal to the number of advertising campaigns in all accounts.

After the introduction of this lemma, we can talk about combining advertising campaigns into packages, so that the package corresponds to the media plan node. Now our task will be formulated as follows:

It is necessary to distribute the budget for campaigns in a batch in such a way as to maximize the number of purchased conversions for a given budget.

This seems to be very similar to the formulation of the classical knapsack problem . The volume of the backpack is the size of the budget, and the value of the stones is the data on the cost of conversion. But this is only partly true. The fact is that the budget for advertising campaigns can be selected in any fractional way (up to the limits of the AC capacity), and the stones in the backpack problem are not separable. There is a variation of this problem - the continuous knapsack problem . Apparently its wording is more suitable, perhaps even this is it (if you have any comments on this, I will be glad to read them).



It also seems to me that having made a mistake in the original name of the problem, I nevertheless chose a suitable solution using a greedy algorithm. When I figured out the approaches to solving and methods for solving the knapsack problem, I could not apply the dynamic programming method to solve my case (apparently, the reason is precisely in the fractionality). But the greedy algorithm, according to my calculations, fit, in fact, it solves the continuous knapsack problem.



In a nutshell: Bundle campaigns should line up in ascending order of actual cost per conversion. Those campaigns that can spend more and are at the top of the list should be given this opportunity. Those campaigns that are at the bottom of the list in the event of a budget deficit should be cut first. Thus, there is a selection of the cheapest RK for the specified budget in the package.

• - , , . .
• Google. :)

• , .. . . .
• , .. ,

• ( )

1. , Google Analytics
2. the resulting report must be stored somewhere, in this case any database is suitable, but the most convenient for my taste is Google BigQuery
3. You can use Jupyter notepad to analyze data and build reports. Also, for my taste, Google Colab is better. easy teamwork is organized (like in Google Docs)
4. You need a server that will periodically run the re-budgeter and collect statistics, usually almost any standard AWS or Google Cloud cloud server is enough for such a task.
5. There are options, for campaigns at the bottom of the list, he assigns a minimum budget, before suspension. But you need to think over the mechanism of periodic "rehabilitation" of such campaigns and answer the question where to get the data on the cost of conversion, if the campaign has long been stopped

So far, I have everything.



Thank you for attention.