Combinatorial optimization
From Free net 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.
Combinatorial optimization algorithms are often implemented in an efficient imperative programming language, in an expressive declarative programming language such as Prolog, or some compromise, perhaps a functional programming language such as Haskell, or a multi-paradigm language such as LISP.
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 |
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 <math>(X,P,Y,f,\mathrm{extr})</math> 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).
Example problems
Methods
Heuristic search methods (metaheuristic algorithms) as those listed below have been used to solve problems of this type.
- local search
- Simulated annealing
- GRASP
- Swarm intelligence
- Tabu search
- Genetic algorithms
- Ant colony optimization
- Reactive search
See also
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.
- 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 0486402584.