## Definition **Combinatorial optimisation** is the study of optimisation problems where the decision variables take values in a discrete set — typically subsets, permutations, paths, or assignments. The vast majority of these problems are **NP-hard**, but practical solvers handle large instances every day. ## Canonical Problems - **Travelling Salesman Problem (TSP).** Find the shortest tour visiting all cities. - **Knapsack.** Select items maximising value subject to weight limit. - **Bin packing.** Pack items into the fewest bins. - **Graph colouring.** Colour vertices so adjacent ones differ. - **Vertex cover, set cover.** Choose minimum subset to "cover" all elements/edges. - **Maximum independent set / clique.** - **Job shop scheduling.** ## Algorithmic Approaches ### Exact Methods For when optimal solutions are required. - **[[Branch and Bound]].** Systematic enumeration with pruning. Foundation of integer programming. - **[[Branch and Cut]].** Branch-and-bound enhanced with cutting planes. - **[[Dynamic Programming]].** For problems with optimal substructure (knapsack, shortest path). - **Constraint Programming.** Domain-reduction + search for combinatorial problems (see [[Constraint Satisfaction Problem]]). Modern MILP solvers (Gurobi, CPLEX, OR-Tools CP-SAT) routinely solve "hard" combinatorial problems with thousands of variables. ### Approximation Algorithms Polynomial-time algorithms with provable bounds on solution quality. - **2-approximation for vertex cover** (greedy edge selection). - **2-approximation for TSP** with triangle inequality. - **PTAS / FPTAS** for some problems (knapsack has an FPTAS). For NP-hard problems where approximation guarantees matter, this is the rigorous path. ### Heuristics and Metaheuristics When optimality matters less than getting a good solution fast. - **Greedy algorithms.** Fast; often surprisingly good. - **Local search.** Start from a solution; explore neighbours. - **[[Simulated Annealing]], [[Genetic Algorithms]], [[Tabu Search]], [[Particle Swarm Optimization]].** Modern industrial practice: combine MILP for parts of the problem with metaheuristics for the rest. ## Why It's Hard The discrete structure creates combinatorial explosion. A TSP with 25 cities has $\sim 10^{24}$ tours. Pure enumeration is hopeless; algorithmic cleverness is essential. Most combinatorial problems are NP-hard — no polynomial-time algorithm is known and (if $P \neq NP$) none exists. ## Polynomial-Time Combinatorial Problems A few are tractable: - **Shortest path** (Dijkstra, Bellman-Ford, Floyd-Warshall). - **Maximum bipartite matching** (Hopcroft-Karp). - **Minimum spanning tree** (Kruskal, Prim). - **Maximum flow / min cut** (Ford-Fulkerson, Edmonds-Karp). - **Linear assignment** (Hungarian algorithm). These polynomial-time algorithms often serve as subroutines in algorithms for harder problems. ## The Role of LP Relaxation A common technique: take an [[Integer Linear Programming]] problem and *drop* the integrality constraints. Solve the LP — it's polynomial. Use the LP solution as: - A bound (the LP optimum is at least as good as the ILP optimum for minimisation). - A guide (round, repair, or branch on the LP solution). This is the foundation of branch-and-bound for MILP. ## When You Need an MILP Solver For real-world combinatorial problems with structure (logistics, scheduling, network design), reach for a commercial MILP solver. They're orders of magnitude faster than hand-coded algorithms for most domains. ## Related - [[Integer Linear Programming]] - [[Branch and Bound]] - [[Dynamic Programming]] - [[Constraint Satisfaction Problem]] - [[Combinatorial-planning-problem (CPP)]]