Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.

A study of computational complexity theory helps to motivate combinatorial optimization. Combinatorial optimization algorithms are typically concerned with problems that are NP-hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e.g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.

Informal definition

The domain of combinatorial optimization is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution.

Formal definition

An instance of a combinatorial optimization problem can be described in a formal way as a tuple (X,P,Y,f,extr) where

X is the solution space (on which f and P are defined)

P is the feasibility predicate.

Y is the set of feasible solutions.

f is the objective function.

extr is the extreme (typically min or max).

Example problems

Vehicle routing problem

Traveling salesman problem

Minimum spanning tree problem

Linear programming (if the solution space is the choice of which variables to make basic)

Eight queens puzzle. (A constraint satisfaction problem. When applying standard combinatorical optimization algorithms to this problem, one would typically treat the goal function as the number of unsatisfied constraints (say number of attacks) instead of as a single boolean signifying whether the whole problem is satisfied or not.)

Knapsack problem

Methods

Heuristic search methods (metaheuristic algorithms) as those listed below have been used to solve problems of this type.

Local search

Simulated annealing

Quantum annealing

GRASP

Swarm intelligence

Tabu search

Genetic algorithms

Ant colony optimization

Reactive search

Bees algorithm