Combinatorial Problems

Optimization · Axiom Academy

Explore classic problems where choosing the right combination matters The Traveling Salesman Problem Click cities in order to create a route that visits all 5 cities and returns home. Try to find the shortest route! You have a backpack with capacity 15 kg. Select items to maximize value without exceeding capacity: Match 4 workers to 4 tasks. Each worker can do exactly one task. Click a worker, then click a task to assign: Watch how the number of possible solutions explodes as problem size increases: Combinatorial problems involve selecting, ordering, or matching discrete objects. Solutions are combinations or permutations - not continuous values. The number of possible solutions grows exponentially with problem size. A 20-city TSP has quintillions of possible tours. TSP: shortest route visiting all cities. Knapsack: maximize value within capacity. Assignment: optimal one-to-one matching. Many real problems reduce to these. Brute force is impossible for real problems. We use branch and bound (exact), heuristics (fast approximations), and metaheuristics (intelligent search).

This is the written version of the interactive lesson above. See the full Optimization course.