Combinatorial Optimization

Combinatorial optimization is the branch of mathematics and computer science that asks how to choose the best arrangement from a finite—but usually astronomically large—set of possibilities.

16 frameworks, from 1935 to today · Combinatorics · Mathematics

still a working view ended · each leads to its entry below

Overview

Combinatorial optimization is the branch of mathematics and computer science that asks how to choose the best arrangement from a finite—but usually astronomically large—set of possibilities1. Which routes should a delivery fleet take1? How should jobs be scheduled on machines1? Which edges of a network carry the most flow2? What is the cheapest way to connect a set of cities3? The objects are discrete: routes, matchings, schedules, subsets, orderings14. The goal is an optimum: least cost, greatest profit, shortest distance, maximum throughput.

What makes the field distinctive is the tension between easy statements and hard solutions. A problem can be described in a sentence and still resist every known algorithm on large inputs. Much of the history of combinatorial optimization is the story of learning to live with that tension—by finding special structures that make hard problems easy, by proving that some problems are genuinely hard, and by building methods that give provably good answers even when perfect ones are out of reach.

Origins in Networks and Flows

The field's first great result came from an unexpected place. In 1930, the Hungarian mathematician Dénes Kőnig proved that in any bipartite graph—a network whose vertices split into two groups with edges only between the groups—the maximum number of edges in a matching equals the minimum number of vertices needed to cover all edges. This duality between a maximization and a minimization was more than a curiosity: it showed that certain optimization problems have a hidden structure that certifies optimality.

The practical push came from logistics and military planning. During World War II, problems of transporting supplies and assigning personnel to tasks demanded systematic methods5. George Dantzig, working on linear programming at the U.S. Air Force, developed the simplex method in 1947. Linear programming optimizes a linear objective subject to linear constraints over continuous variables; the simplex method walks along the edges of a polyhedron from vertex to vertex until no improvement is possible. Its success raised an obvious question: what happens when the variables must be whole numbers—when you cannot send half a truck?

The Integer Programming Problem and Its Geometry

Requiring variables to be integers turns linear programming into integer programming, and the change is drastic. In 1958, Ralph Gomory introduced cutting-plane methods: solve the continuous relaxation, and if the answer is fractional, add a new constraint—a cut—that excludes the fractional solution without excluding any integer one, then re-solve. The idea is elegant and finite, but in practice the cuts can pile up and numerical difficulties slow convergence.

A deeper structural insight came from polyhedral combinatorics, the study of the geometric shapes defined by combinatorial constraints6. In 1954, Dantzig, Ray Fulkerson, and Selmer Johnson solved a 49-city traveling salesman problem—find the shortest tour visiting every city once—by describing the convex hull of all tours through linear inequalities and solving the resulting linear program. The tour polytope became a model: if you can characterize the facets of the convex hull of feasible solutions, you can optimize over it with linear programming. This line of work, pursued through the 1960s and 1970s by Jack Edmonds, Václav Chvátal, and others, produced complete descriptions for matchings, spanning trees, and other structures, and it remains a central engine of modern solvers.

Matchings, Flows, and the Rise of Good Algorithms

The 1950s and 1960s also saw the birth of combinatorial algorithms as a discipline. In 1956, Lester Ford and Delbert Fulkerson gave the augmenting-path method for maximum flow in a network: start with no flow, find a path from source to sink with spare capacity, push flow along it, repeat. The max-flow min-cut theorem—that the maximum flow equals the minimum capacity of a cut separating source from sink—generalized Kőnig's duality and became a template for a whole family of results.

Jack Edmonds's 1965 blossom algorithm for maximum matching in general (non-bipartite) graphs was a landmark of a different kind. Earlier methods worked for bipartite graphs; general graphs defeated them because of odd cycles. Edmonds's algorithm contracts odd cycles—"blossoms"—into single vertices, solves the reduced problem, and then expands them. It was also Edmonds who, in 1965, drew the crucial distinction between problems solvable in time polynomial in the input size and those for which no such method was known, arguing that polynomial-time solvability is the right formal notion of an "efficient" algorithm7.

Hardness, and the Meaning of "Hard"

The 1970s brought a reckoning. In 1971, Stephen Cook proved that the Boolean satisfiability problem is NP-complete: every problem whose solution can be checked quickly can be reduced to it, so a fast algorithm for satisfiability would yield fast algorithms for all of them. Richard Karp's 1972 paper extended this to twenty-one combinatorial problems, including the traveling salesman problem, graph coloring, and set cover. The implication was stark: unless $P = NP$—an open question to this day—no polynomial-time algorithm exists for these problems.

This did not end the field; it redirected it. If exact solutions are out of reach in general, three responses emerged. One was to identify special cases that remain tractable. Another was to accept exponential worst-case time but design methods that work well on real instances. The third was to give up exactness and aim for provable approximation.

Branch and Bound, Dynamic Programming, and the Exact Tradition

Branch and bound, developed in the early 1960s by Ailsa Land and Alison Doig for integer programming, embodies the second response8. It systematically partitions the solution space into subproblems (branching) and discards any subproblem whose relaxed bound cannot beat the best solution found so far (bounding)8. With good bounds, vast regions of the search tree are pruned. Modern mixed-integer programming solvers—CPLEX, Gurobi, and the open-source SCIP—are sophisticated descendants of this idea, combining branch and bound with cutting planes, preprocessing, and heuristics. They routinely solve industrial problems with thousands of integer variables, even though the worst case remains exponential.

Dynamic programming, formalized by Richard Bellman in the 1950s, takes a different route to exactness9. It solves a problem by breaking it into overlapping subproblems, solving each once, and storing the results9. The shortest path in a graph, the optimal parenthesization of a matrix product, and the knapsack problem all yield to this approach when the state space is manageable. The method's limitation is the "curse of dimensionality": the number of subproblems can grow exponentially with the input's parameters10.

Greedy algorithms and matroids form a third exact tradition. A greedy algorithm builds a solution piece by piece, always taking the locally best available choice11. For most problems this fails, but in 1935 Bartel van der Waerden and independently in the 1950s Hassler Whitney introduced matroids—abstract structures capturing the essence of linear independence—and it turned out that greedy algorithms are exactly optimal on matroids. The minimum spanning tree problem, solved greedily by Joseph Kruskal in 1956 and by Robert Prim in 1957, is the canonical example. Matroid theory, developed by Whitney and later by Gian-Carlo Rota and others, gave combinatorial optimization a general theory of when local choices suffice.

Approximation: Guarantees Without Perfection

When exactness is impossible, approximation algorithms offer a certificate of quality12. A ρ-approximation algorithm runs in polynomial time and produces a solution within a factor ρ of optimal. In the 1970s and 1980s, researchers built a catalogue of such results: the greedy algorithm for set cover gives a logarithmic approximation; Christofides's 1976 algorithm for the metric traveling salesman problem guarantees a tour at most 1.5 times optimal; the 1990s saw the development of semidefinite programming relaxations, notably Michel Goemans and David Williamson's 1995 algorithm for max-cut with a 0.878 guarantee.

A parallel line of work asked how good an approximation is possible. The PCP theorem, proved in the 1990s by Sanjeev Arora, Shafi Goldwasser, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, showed that many problems cannot be approximated better than certain thresholds unless $P = NP$. Approximation had become a two-sided theory: what can be achieved, and what cannot.

Approximation schemes refine the picture further. A polynomial-time approximation scheme (PTAS) gives, for any fixed ε > 0, a (1+ε)-approximation in polynomial time13. Some problems admit a fully polynomial-time approximation scheme (FPTAS), where the running time is polynomial in both input size and 1/ε1. Parameterized complexity, developed from the 1990s by Rod Downey and Michael Fellows, asks whether a problem can be solved in time f(k) · $n^c$ where k is a structural parameter—the size of a solution, the treewidth of a graph—and f is any function. Fixed-parameter tractability identifies a different kind of tractability, one measured against structure rather than input size alone.

Heuristics and the Practical Search for Good Solutions

Alongside the provable methods grew a tradition of heuristics: algorithms with no worst-case guarantee but strong empirical performance. Local search, which starts with a solution and repeatedly moves to a better neighbor, is the oldest of these; its refinement, simulated annealing, was introduced by Scott Kirkpatrick, C. Daniel Gelatt, and Mario Vecchi in 1983, borrowing the idea of gradually cooling a metal to escape local optima. Tabu search, genetic algorithms, ant colony optimization, and large neighborhood search followed, forming the family known as metaheuristics—general strategies for guiding a search without committing to a single problem structure. These methods dominate practice in scheduling, routing, and logistics, where instances are large and exact optimality is unattainable.

Submodularity, Online Decisions, and the Modern Landscape

A unifying thread in recent decades has been submodularity14. A set function is submodular if adding an element to a larger set yields no more marginal gain than adding it to a smaller set—a diminishing-returns property14. In 1978, George Nemhauser, Laurence Wolsey, and Marshall Fisher showed that greedy maximization of a monotone submodular function achieves a (1 − 1/e) ≈ 0.632 approximation, a result that underpins influence maximization in social networks, sensor placement, and feature selection. Submodular minimization, by contrast, is polynomial-time solvable, a fact established through the work of Grötschel, Lovász, and Schrijver in the 1980s using the ellipsoid method.

The rise of online and stochastic optimization reflects a world where inputs arrive over time or are uncertain15. In online optimization, decisions must be made without knowledge of future requests; competitive analysis, introduced by Sleator and Tarjan in 1985, measures an online algorithm against an optimal offline one. Stochastic optimization, with roots in Dantzig's 1955 work on linear programming under uncertainty, models randomness explicitly and seeks solutions that perform well in expectation or with high probability. These frameworks now underpin auction design, cloud resource allocation, and revenue management.

The Present

Today combinatorial optimization is a field of many methods held together by shared questions. Mixed-integer programming solvers combine branch and bound, cutting planes, and heuristics into systems of remarkable power16. Approximation algorithms and hardness of approximation define the theoretical frontier. Parameterized complexity and fixed-parameter tractability carve out tractable structure from intractable generality17. Submodular optimization, online algorithms, and stochastic models address settings where the classical assumptions—full information, exact optimality, static input—do not hold. The deepest open question remains the one Karp and Cook framed: whether P equals NP. Around it cluster more specific ones: the exact approximability of the traveling salesman problem in metric spaces, the power of semidefinite and higher-order relaxations, and the design of algorithms that exploit the structure of real instances rather than worst-case inputs. The field's history is a record of learning which structures make hard problems easy, which do not, and how to tell the difference.

References

  1. Combinatorial optimization (introduction, Applications, Specific problems, NP optimization problem), Wikipedia
  2. Maximum flow problem, Wikipedia
  3. Minimum spanning tree, Wikipedia
  4. Optimization problem, Wikipedia
  5. Linear programming (History), Wikipedia
  6. Polyhedral combinatorics, Wikipedia
  7. Computational complexity theory (History), Wikipedia
  8. Branch and bound, Wikipedia
  9. Dynamic programming, Wikipedia
  10. Bellman equation, Wikipedia
  11. Greedy algorithm, Wikipedia
  12. Approximation algorithm, Wikipedia
  13. Polynomial-time approximation scheme, Wikipedia
  14. Submodular set function, Wikipedia
  15. Online optimization, Wikipedia
  16. Branch and cut, Wikipedia
  17. Parameterized complexity, Wikipedia

The frameworks of Combinatorial Optimization

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1935-Present

    Matroid Theory and Greedy Algorithms

    When does a greedy algorithm find the best solution?

    Fly to its tower in Nousfarer

  2. 1950-Present

    Dynamic Programming

    How can we solve a problem by breaking it into overlapping subproblems?

    Fly to its tower in Nousfarer

  3. 1954-Present

    Cutting-Plane Methods

    How can we solve integer programs by adding constraints that cut off fractional solutions?

    Fly to its tower in Nousfarer

  4. 1954-Present

    Polyhedral Combinatorics

    What is the geometric shape of the set of feasible solutions?

    Fly to its tower in Nousfarer

  5. 1955-Present

    Online and Stochastic Optimization

    How do we make decisions without knowing the future?

    Fly to its tower in Nousfarer

  6. 1956-Present

    Network Flow Theory

    How much flow can a network carry?

    Fly to its tower in Nousfarer

  7. 1958-Present

    Integer and Mixed-Integer Programming

    How do we optimize when variables must be whole numbers?

    Fly to its tower in Nousfarer

  8. 1960-Present

    Branch and Bound

    How can we systematically search for the best solution without exploring everything?

    Fly to its tower in Nousfarer

  9. 1970-Present

    Approximation algorithm

    How can we find a solution that is provably close to the best?

    Fly to its tower in Nousfarer

  10. 1971-Present

    Computational complexity theory

    What makes a problem inherently hard to solve?

    Fly to its tower in Nousfarer

  11. 1978-Present

    Submodular set function

    How do we optimize set functions that exhibit diminishing returns?

    Fly to its tower in Nousfarer

  12. 1980-Present

    Metaheuristic

    How can we design general strategies that find good solutions to hard problems?

    Fly to its tower in Nousfarer

  13. 1990-Present

    Approximation Schemes and Parameterized Complexity

    How can we get arbitrarily close to the best solution efficiently?

    Fly to its tower in Nousfarer

  14. 1990-Present

    Hardness of Approximation

    What are the limits of approximating hard problems?

    Fly to its tower in Nousfarer

  15. 1990-Present

    Parameterized Complexity

    How does the difficulty of a problem depend on multiple parameters?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Matroid Theory and Greedy AlgorithmsDynamic ProgrammingCutting-Plane MethodsPolyhedral CombinatoricsOnline and Stochastic OptimizationNetwork Flow TheoryInteger and Mixed-Integer ProgrammingBranch and BoundApproximation algorithmLocal SearchComputational complexity theorySubmodular set functionMetaheuristicApproximation Schemes and Parameteriz…Hardness of ApproximationParameterized Complexity

Beyond the field

Where Combinatorial Optimization's ideas came from in other fields, and what they led to there: the strongest 12 of 57 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Combinatorial Optimization is a planet in Nousfarer

Its city has a tower for each of these 16 frameworks. Land, walk in, and climb one concept at a time.

Land on Combinatorial Optimization

Related fields

Fields its ideas are linked to

More in Combinatorics

See where Combinatorial Optimization sits on the Map of Human Knowledge