Combinatorial optimization

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.

Some research literature ^[1] considers discrete optimization to consist of integer programming together with combinatorial optimization (which in turn is composed of optimization problems dealing with graphs, matroids, and related structures) although all of these topics have closely intertwined research literature.

Example problems

• Vehicle routing problem
• Traveling salesman problem (TSP)
• Minimum spanning tree problem
• Linear programming (if the solution space is the choice of which variables to make basic)
• Integer programming
• 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

Methods

There is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization, a considerable amount of it unified by the theory of linear programming. Some examples of combinatorial optimization problems that fall into this framework are shortest paths and shortest path trees, flows and circulations, spanning trees, matching, and matroid problems.

For NP-complete discrete optimization problems, current research literature includes the following topics:

• polynomial-time exactly-solvable special cases of the problem at hand (e.g. see fixed-parameter tractable)
• algorithms that perform well on "random" instances (e.g. for TSP)
• approximation algorithms that run in polynomial time and find a solution that is "close" to optimal
• solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behaviour inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes ^[2])

Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items, therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. However, generic search algorithms are not guaranteed to find an optimal solution, nor are they guaranteed to run quickly (in polynomial time). (Since some discrete optimization problems are NP-complete, e.g. the travelling salesman problem, this is expected unless P=NP.)

References

1. ^ "Discrete Optimization". Elsevier. http://www.elsevier.com/locate/disopt. Retrieved 2009-06-08. 
2. ^ Bill Cook. "Optimal TSP Tours". http://www.tsp.gatech.edu/optimal/index.html. Retrieved 2009-06-08. 

• 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)
• Journal of Combinatorial Optimization

External links

• Integer programming notes, J E Beasley.