Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory.

Sometimes it is called "discrete optimization", however the latter term is considered to be somewhat different.

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.

Examples of problems are the traveling salesman problem, the minimum spanning tree problem, and linear programming problems.

Heuristic search methods (meta heuristics), such as local search, simulated annealing, tabu search, or genetic algorithms can be used to find optimal solutions of combinatorial optimization problems. A question of great interest concerns the efficiency of such methods, i.e. the question of whether one search method is better than the other across all types of problems. An answer to this question was provided in the 90's by the no-free-lunch theorem.

References

• William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.
• Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.

Journals

• Journal of Combinatorial Optimization (http://www.kluweronline.com/issn/1382-6905)