Combinatorial optimization
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] 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 combinatorial optimization algorithms to this problem, one would usually treat the goal function as the number of unsatisfied constraints (say number of attacks) rather than as a single boolean indicating whether the whole problem is satisfied or not.)
- Knapsack problem
- Cutting stock problem
[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)
