Combinatorial optimization

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Combinatorial optimization is a branch of optimization. Its domain 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.

It is a branch of 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.


[edit] Example problems

[edit] Methods

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

[edit] See also

A question of great interest is whether one search method is superior in performance to others across all problems. For a broad class of algorithms, the answer is no:

[edit] References

  • Alexander Schrijver; A Course in Combinatorial Optimization February 1, 2006 (© A. Schrijver)
  • William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 0-471-55894-X.
  • Jon Lee; "A First Course in Combinatorial Optimization"; Cambridge University Press; 2004; ISBN 0-521-01012-8.
  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
  • Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4.
  • Arnab Das and Bikas K. Chakrabarti (Eds.) Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)

[edit] Journals

Personal tools