COMBINATORIAL OPTIMIZATION

'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

Informal definition

Formal definition

Example problems

Methods

See also

References

Journals

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
$(X,P,Y,f,mathrm\{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).

Example problems

★ Traveling salesman problem

★ Minimum spanning tree problem

★ Linear programming

★ Eight queens puzzle

★ Knapsack problem

Methods

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

★ Local search

★ Simulated annealing

★ Quantum annealing

★ GRASP

★ Swarm intelligence

★ Tabu search

★ Genetic algorithms

★ Ant colony optimization

★ Reactive search

See also

★ Discrete optimization

★ Search algorithm

★ Brute-force search
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:

★ No free lunch in search and optimization

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.

★ 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)

Journals

★ Journal of Combinatorial Optimization

★ Discrete Optimization