A Problem Larger Than the Universe

In this puzzle, you are not asked to solve a concrete optimization problem, but to provide an estimate. Easy?

The quadratic assignment problem is a classical facility location problem. We are given n facilities that have known traffic volumes between each pair of facilities. We are also given n locations with known distances between each pair of locations. The task is simple: Assign each facility to a location so as to minimize the total transportation costs. We obtain these costs by multiplying the volume times the distance between each pair of facilities and then summing them all.

Say, we employ a brute-force algorithm to find the min-cost assignment. And we use a very large and very fast computer. And we have a lot of time.

We have one processor for each atom in the universe. That is 10^82 processors. Each processor can evaluate the cost of an assignment in Planck-time, 10^43 solutions per second. Note that no physical phenomenon can be measured faster. And we run this insane machine for 16 Billion years, from the Big Bang until now.

Take a guess, do not compute: How many facilities can we have maximally so that our machine can still solve this one instance?

What do you think? Is it more or less than a thousand?

The maximum we can hope to tackle with this brute force approach is one single QAP instance with 93 facilities.

And that is what optimization is all about: To solve real-world sized problems to near-optimality in a time that is suited for the problem. And that means, not to look at every potential solution as this takes way too much time.

We built InsideOpt Seeker to solve problems like the QAP in very short time. Below, we compare the performance of Seeker with Gurobi and Hexaly on the Taillard instances, some of which have 100 or more facilities. You see one triangle for each instance, positioned at the gap to the best-known solution that each solver leaves at the time limit. We used a four-core AMD EPYC x86_64, ubuntu-24_04-lts Linux machine with 5.5MB cache for these experiments.

You can try out Seeker yourself. Just check out this Google Colab. Here, we stop Seeker when the Hexaly or Gurobi gap after one hour is reached and measure how much faster Seeker is. Under 'Runtime' click 'Run all'. When that comparison is finished, look for 'Gurobi = True' after the definition of solveQAP - setting it to False creates a comparison with Hexaly.

Why do we compare for speed? Because speed matters. A super-efficient plan one minute too late is worth nothing. We need the best possible plans in time to change the world for the better. That is the core belief that drives InsideOpt. That we can change the world by increasing efficiency.

Now you are welcome to venture another guess how much faster is Seeker than Hexaly, more or less than 10 times? And Seeker vs Gurobi? Do you think Seeker is more or less than 100 times faster than Gurobi?