- Atlas
- Mathematics
- Combinatorial Optimization
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
- Matroid Theory and Greedy Algorithms 1935-Present
- Dynamic Programming 1950-Present
- Cutting-Plane Methods 1954-Present
- Polyhedral Combinatorics 1954-Present
- Online and Stochastic Optimization 1955-Present
- Network Flow Theory 1956-Present
- Integer and Mixed-Integer Programming 1958-Present
- Branch and Bound 1960-Present
- Approximation algorithm 1970-Present
- Local Search 1970-Present
- Computational complexity theory 1971-Present
- Submodular set function 1978-Present
- Metaheuristic 1980-Present
- Approximation Schemes and Parameterized Complexity 1990-Present
- Hardness of Approximation 1990-Present
- Parameterized Complexity 1990-Present
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
- Combinatorial optimization (introduction, Applications, Specific problems, NP optimization problem), Wikipedia
- Maximum flow problem, Wikipedia
- Minimum spanning tree, Wikipedia
- Optimization problem, Wikipedia
- Linear programming (History), Wikipedia
- Polyhedral combinatorics, Wikipedia
- Computational complexity theory (History), Wikipedia
- Branch and bound, Wikipedia
- Dynamic programming, Wikipedia
- Bellman equation, Wikipedia
- Greedy algorithm, Wikipedia
- Approximation algorithm, Wikipedia
- Polynomial-time approximation scheme, Wikipedia
- Submodular set function, Wikipedia
- Online optimization, Wikipedia
- Branch and cut, Wikipedia
- 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.
- 1935-Present
Matroid Theory and Greedy Algorithms
When does a greedy algorithm find the best solution?
- 1950-Present
Dynamic Programming
How can we solve a problem by breaking it into overlapping subproblems?
- 1954-Present
Cutting-Plane Methods
How can we solve integer programs by adding constraints that cut off fractional solutions?
- 1954-Present
Polyhedral Combinatorics
What is the geometric shape of the set of feasible solutions?
- 1955-Present
Online and Stochastic Optimization
How do we make decisions without knowing the future?
- 1956-Present
- 1958-Present
Integer and Mixed-Integer Programming
How do we optimize when variables must be whole numbers?
- 1960-Present
Branch and Bound
How can we systematically search for the best solution without exploring everything?
- 1970-Present
Approximation algorithm
How can we find a solution that is provably close to the best?
- 1970-Present
- 1971-Present
Computational complexity theory
What makes a problem inherently hard to solve?
- 1978-Present
Submodular set function
How do we optimize set functions that exhibit diminishing returns?
- 1980-Present
Metaheuristic
How can we design general strategies that find good solutions to hard problems?
- 1990-Present
Approximation Schemes and Parameterized Complexity
How can we get arbitrarily close to the best solution efficiently?
- 1990-Present
Hardness of Approximation
What are the limits of approximating hard problems?
- 1990-Present
Parameterized Complexity
How does the difficulty of a problem depend on multiple parameters?
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.
Integer and Mixed-Integer Programming grew out of Cutting-Plane Methods
Gomory's cutting-plane method was developed as a general algorithm for integer programming, directly extending the cutting-plane idea to the integer case.
Carried by Ralph Gomory.
Approximation Schemes and Parameterized Complexity grew out of Approximation algorithm
Approximation schemes are a refinement of approximation algorithms, providing a trade-off between running time and approximation ratio.
Metaheuristic grew out of Local Search
Metaheuristics such as simulated annealing and tabu search are generalizations of local search that allow escaping local optima.
Hardness of Approximation grew out of Computational complexity theory
Hardness of approximation is a branch of computational complexity theory that studies the inapproximability of optimization problems.
Parameterized Complexity grew out of Computational complexity theory
Parameterized complexity is a subfield of computational complexity theory that classifies problems by multiple parameters.
Submodular set function influenced by Matroid Theory and Greedy Algorithms
Submodular set functions generalized the rank function of a matroid, and early work on submodular optimization built directly on matroid theory.
Carried by Jack Edmonds.
Branch and Bound influenced by Dynamic Programming
Branch and bound for integer programming often uses dynamic programming to compute bounds for subproblems, as in the knapsack problem.
Carried by Richard Bellman.
Approximation algorithm influenced by Dynamic Programming
Approximation algorithms for problems like knapsack and scheduling frequently employ dynamic programming as a subroutine to achieve performance guarantees.
Approximation Schemes and Parameterized Complexity influenced by Dynamic Programming
Approximation schemes and parameterized algorithms often use dynamic programming over bounded treewidth or other parameters to obtain fixed-parameter tractability.
Branch and Bound influenced by Cutting-Plane Methods
Branch and bound for integer programming incorporates cutting planes to tighten relaxations and improve bounds, as in branch-and-cut.
Integer and Mixed-Integer Programming influenced by Polyhedral Combinatorics
Polyhedral combinatorics provided the geometric foundation for integer programming by characterizing the convex hull of feasible integer points.
Approximation algorithm influenced by Polyhedral Combinatorics
Approximation algorithms often use linear programming relaxations and polyhedral techniques to derive performance guarantees, such as the rounding of LP solutions.
Approximation algorithm influenced by Integer and Mixed-Integer Programming
Approximation algorithms for integer programming problems often use LP relaxations and rounding techniques derived from integer programming theory.
Hardness of Approximation influenced by Approximation algorithm
Hardness of approximation arose from the need to establish limits on the performance of approximation algorithms, using the PCP theorem.
Carried by Sanjeev Arora.
Approximation Schemes and Parameterized Complexity influenced by Computational complexity theory
Parameterized complexity and approximation schemes both emerged from computational complexity theory, using complexity classes to classify problem difficulty.
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.
Cutting-Plane Methods grew out of Linear Programming in Mathematical Optimization
Cutting-plane methods grew directly out of linear programming: Gomory's 1958 fractional cutting-plane algorithm added valid inequalities to a simplex tableau to solve integer programs, and Kelley's 1960 method cut a linear program against a convex nonlinear objective.
Carried by Ralph E. Gomory; James E. Kelley Jr..
Integer and Mixed-Integer Programming influenced LP rounding and primal-dual in Approximation Algorithms
Integer and mixed-integer programming supplied the LP relaxations whose rounding and duals define this framework. The primal-dual schema for approximation was adapted from LP duality and the LP/IP relaxation gap central to integer programming.
Integer and Mixed-Integer Programming grew out of Linear Programming in Mathematical Optimization
Integer programming grew out of linear programming: Gomory's cutting-plane method (1958) and the branch-and-bound work of Land and Doig (1960) took the simplex method and LP duality as their starting machinery, adding integrality constraints on top.
Carried by Ralph Gomory; Ailsa Land; Alison Doig.
Integer and Mixed-Integer Programming grew out of Linear Programming in Operations Research
Integer and mixed-integer programming was built directly on the linear-programming model developed in operations research, using LP relaxations as bounds and the simplex method as its core subroutine.
Carried by Ralph Gomory; George Dantzig.
Branch and Bound influenced by Linear Programming in Mathematical Optimization
Branch and bound was introduced by Land and Doig in 1960 as a method for integer linear programming, using LP relaxations to compute bounds and branching on fractional variables.
Carried by Ailsa Land; Alison Doig.
Branch and Bound influenced by Linear Programming in Operations Research
The branch-and-bound procedure was devised within operations research to solve integer programs, relying on LP relaxation bounds from the simplex method at each node.
Carried by Ailsa Land; Alison Doig.
Approximation algorithm led to Polynomial-time approximation scheme in Approximation Algorithms
The polynomial-time approximation scheme is a refinement of the approximation algorithm: it demands a family of algorithms with a tunable error parameter rather than a single fixed-ratio guarantee. The PTAS concept grew directly out of the approximation-algorithm literature of the early 1970s.
Approximation algorithm led to Resource-constrained approximation in Approximation Algorithms
Resource-constrained approximation is a branch of approximation algorithms that adds budget or resource constraints to the optimisation, growing out of the standard approximation framework. It refines the approximation-algorithm programme to constrained settings such as budgeted and knapsack-constrained problems.
Local Search led to Metaheuristic in Mathematical Optimization
Metaheuristics grew directly out of local search: simulated annealing, tabu search and genetic algorithms all wrap or extend neighbourhood search, and local search remains the inner loop of most metaheuristics.
Computational complexity theory led to Parameterized complexity in Graph Algorithms
Parameterized complexity grew out of computational complexity theory, generalising NP-hardness by asking how hardness depends on a parameter and introducing the W-hierarchy as a refinement of NP. Downey and Fellows built directly on the classical complexity framework.
Carried by Rodney Downey; Michael Fellows.
Computational complexity theory influenced Proof Complexity in Theory Of Computation
Computational complexity theory supplied proof complexity with its central question, whether NP equals coNP, which Cook and Reckhow showed is equivalent to the existence of a polynomially bounded proof system. The resource-bounded viewpoint passed directly into proof theory.
Carried by Stephen Cook; Robert Reckhow.
Computational complexity theory led to Fine-Grained Complexity in Complexity Theory
Fine-grained complexity is a later branch of the same computational complexity theory tradition, refining its coarse polynomial-versus-exponential classifications into exact exponent bounds. It inherits the Turing-machine model, reductions and NP-completeness framework established in the 1970s.
Carried by Stephen Cook; Richard Karp.

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 OptimizationRelated fields
Fields its ideas are linked to
- Approximation Algorithms 12 links
- Algorithms 7 links
- Mathematical Optimization 6 links
- Complexity Theory 6 links
- Graph Algorithms 4 links
- Parameterized Algorithms 4 links
- Operations Research 3 links
- Combinatorics 3 links
- Theory Of Computation 2 links
- Planning And Search 1 link
- Randomized Algorithms 1 link
- Numerical Analysis 1 link
More in Combinatorics
- Additive Combinatorics
- Algebraic Combinatorics
- Coding Theory
- Combinatorics
- Design Theory
- Enumerative Combinatorics
- Extremal Combinatorics
- Graph Theory
- Matroid Theory
- Order Theory
- Probabilistic Combinatorics
See where Combinatorial Optimization sits on the Map of Human Knowledge