Today I learned, there is Google OR-Tools project aiming to solve combinatorial optimization problems.
OR-Tools is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.
What is "combinatorial optimization" problem, after all?
Imagine you have € 15000 in your pocket, and you want to spend them on Google AdWords to advertise your small business. Google offers you a table from which you can choose keywords for your advertisement campaign.
Spending day and night, you finally selected over 300 keywords that describe your business very well. When you run your advertisement campaign, Google will surely bring some traffic to your website.
But now you wonder, is this setup really optimal? Do I get the maximum clicks for the money I spend?
It turned out if you only select keywords and set your daily budget, then your campaign will be far from optimal. People click on your advertisements, and your website receives some traffic, but you can have 3 to 5 times more visitors if you optimize your campaign!
The root of this optimization lies in the fact that the amount of clicks you get is not proportional to the money you invest. You might think "if I spend two times more money, I'll get two times more visitors," but this is rarely the case.
What should you do?
Playing a bit with Google AdWords, you noticed, that there are about 15 different levels of prices for keywords (note: in reality, there are way more levels). And now we have 300 keywords we want to use in advertisement and 15 price levels for each keyword.
Look, here is the number of possible combinations you need to check to find the most optimal setup for your campaign.
I would call it Huuuuuuuuuuuuuuuuge.
But you are not alone. The problem you are struggling with is one of a well-known problem in Computer Science. We call it the Knapsack Problem. One of the tools in the Google OR-Tools allows you to solve the Knapsack Problem efficiently in you know how to program in C++, Python, C#, or Java.
The solution is the keyword plan (a list of keywords and their maximum prices) which maximizes the number of clicks for the budget you have.
Jun 24, 2019. Berlin