Google OR-Tools
Today I learned about Google OR-Tools, an open-source suite for optimization: vehicle routing, flows, integer and linear programming, and constraint programming.
What is a "combinatorial optimization" problem, anyway? Imagine you have €15,000 to spend on Google AdWords for a small business. Google hands you a table of keywords. You spend days picking three hundred or so that describe your business well, set a daily budget, and launch. Traffic arrives. But is the setup optimal? Are you getting the most clicks for your money?
With around fifteen price levels per keyword (in reality, many more) and three hundred keywords, the number of combinations you would have to check is absurd:
67201306530145677691227706450599008677218833635331469498134353103850815627567935203598418279174424696301669832711078926054889744719967996576630443115841300927690884038379151711968495939730373490224964349010505512135479212699421321404087209170778595312054887078716487128925063696497496197915895863887572847552285583427877924123094999231398105621337890625
You are not the first to face it, though. This is a classic of computer science, the Knapsack Problem, and OR-Tools will solve it efficiently for you, whether you write C++, Python, or a few other languages.