What is Combinatorial Optimization?
#
Imagine you are a Data Scientist working for an airline and are told to find the optimal flight schedule for the week to maximize the number of flights subject to constraints such as fuel and airspace.
How would you do this?
Well, you could try every possible solution, this is called _brute-force search, however what if I told you we were going to do 500 flights? The number of different combinations you would need to try would be on a scale of ~500! which is roughly equal to 1.22 x 10¹¹³⁴. This ** number is unimaginably huge and makes brute-force search intractabl**_e.
So, how do you solve this problem?
Combinatorial Optimization!
_Combinatorial optimization_ deals with finding an optimal solution from finite objects where the problem is intractable. This sounds very much like our problem above!
In fact, combinatorial Optimization is used in sundry fields:
- Logistics and supply chain
- Manufacturing
- Finance
- Healthcare
This makes it an essential skill for Data Scientists to understand and develop the know-how to effectively deal with these types of problems.
To learn more about combinatorial optimization methods, which are mainly meta-heuristic, you can check out some of my previous posts here:
How To Solve Travelling Salesman Problem With Simulated Annealing
However, in this post, I want to truly explore why these types of problems are difficult and demonstrate how a simple problem literally ‘blows up' in complexity.
An Old Favourite: Travelling Salesman Problem
A staple example of a combinatorial optimization problem is the _traveling salesman problem (TSP)_. This is a very simple problem that asks the question:
‘Find the shortest route through a set of cities, that visits every city once and finishes at the origin city'
Sounds simple right? In realistic scenarios, this is far from the truth.
This is because the number of possible solutions to this problem leads to a _combinatorial explosion_ as more cities are added to the route. The number of solutions to the TSP is:
Where n is the number of cities.
Lets use some actual numbers to really show this ‘explosion‘:
- n = 4: solutions = 3
- n = 8: solutions = 2,520
- n = 16: solutions = 1.0461395 x 10¹³
What's even more telling is that for 20 cities it takes approximately 1,900 years to solve the TSP by brute-force!
Demonstrating a Combinatorial Explosion
Let's really now dig in with some code to fully understand the inner workings of the brute-force algorithm and portray the combinatorial explosion.
Below is a boilerplate class for solving the TSP using brute-force search:
Let's now use the algorithm on some dummy ‘fake' city data to confirm it indeed returns the best solution:
Looks good! The initial solution is clearly non-optimal and the final best solution appears visually to be the best.
We will now measure the duration of the brute-force algorithm as a function of the number of cities in the search to graphically depict the combinatorial explosion:
From the above plot, we see that the duration of the brute-force search skyrockets at around 12 cities. To use real numbers, for 11 cities it took ~0.5 minutes, but for 12 cities it took whopping ~36 minutes! So, by just adding an extra city to our search space the algorithm computes time increased by 72 fold!
This genuinely shows the power and intractability of these combinatorial optimization problems.
Summary & Further Thoughts
In this post, we have seen how simple problems can ‘blow up' in complexity. This is common in an industry where we are dealing with large-scale systems and networks. The process of optimizing business problems in these large-scale systems is named combinatorial optimization. The need for this domain stems from the intractability of brute-force search which can take thousands of years to find the best solution to relatively search space. We demonstrated this phenomenon by depicting the combinatorial explosion that occurs for the traveling salesman problem.
Full code used in this post is available on my GitHub here:
Medium-Articles/Optimisation/brute-force at main · egorhowell/Medium-Articles
Another Thing!
I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist. There is no "fluff" or "clickbait," just pure actionable insights from a practicing Data Scientist.
