Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Combinatorial optimization
From Wikipedia, the free encyclopedia
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.
Contents |
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.
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 (usually min or max).
- 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 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
Heuristic search methods (metaheuristic algorithms) as those listed below have been used to solve problems of this type.
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:
- 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.
- 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)