The Quadratic Assignment Problem Explained
Introduction to Combinatorial Optimization
Finding the Best Solution
Imagine you're a delivery driver with a list of cities to visit. You want to find the absolute shortest route that visits each city exactly once before returning home. With just a few cities, you could probably map out all the possible routes and pick the best one. But what if you had 50 cities? The number of possible routes becomes astronomical, far too many to check one by one.
This is the essence of combinatorial optimization. It's the art and science of finding the optimal solution from a finite, but often enormous, set of possible solutions. The goal is to find the "best" option according to some criterion, like the shortest path, the lowest cost, or the highest profit.
This field tackles problems across many industries, from logistics and scheduling to finance and engineering. Anytime you need to make the best choice from a vast number of discrete possibilities, you're dealing with a combinatorial optimization problem.
Counting the Possibilities
To understand the challenge, we need to know how to count the number of possibilities. Two fundamental concepts from combinatorics help us do this: permutations and combinations.
Permutation
noun
An arrangement of objects in a particular order. With permutations, the order of the objects matters.
Think about arranging three books on a shelf. The order you place them in creates a different arrangement. The number of ways to arrange distinct objects is called "n factorial," written as .
Combination
noun
A selection of objects from a collection, where the order of selection does not matter.
Now, imagine you're picking three friends from a group of five to go to the movies. It doesn't matter if you pick Alice, Bob, and then Charlie, or Charlie, Alice, and then Bob. The group is the same. This is a combination.
How Hard Are These Problems?
The number of possibilities in these problems can grow incredibly fast. This rapid growth is often called a "combinatorial explosion." For our delivery driver, the number of routes for cities is . For 10 cities, that's 181,440 routes. For 20 cities, it's over 121 quadrillion. A computer checking a billion routes per second would still take years to finish.
Computer scientists classify problems based on how the time required to solve them scales with the size of the input. This helps us understand which problems are "easy" and which are "hard" for computers.
| Class | What it means | Example |
|---|---|---|
| P | Polynomial time. Problems that are considered "efficiently solvable." A computer can find the solution in a time that grows polynomially (like or ) with the input size . | Finding the shortest path between two specific points in a network. |
| NP | Nondeterministic Polynomial time. Problems where a proposed solution can be verified quickly (in polynomial time), but finding the solution may be very hard. | The traveling salesperson problem. If someone gives you a route, you can easily calculate its total distance. But finding the shortest one is the hard part. |
| NP-hard | "At least as hard as the hardest problems in NP." These are the toughest nuts to crack. If you found an efficient algorithm for one NP-hard problem, you could use it to solve all problems in NP efficiently. | Most famous combinatorial optimization problems, including the traveling salesperson and the quadratic assignment problem, are NP-hard. |
For P problems, we can usually find the single best solution, even for large inputs. For NP-hard problems, however, finding the guaranteed optimal solution is often impossible for anything but small problem sizes. Instead, we often seek very good, but not necessarily perfect, solutions using clever algorithms and heuristics.
What is the primary goal of combinatorial optimization?
You are creating a 4-digit PIN for your bank card, and you cannot repeat any digits. This is an example of a permutation.