Combinatorial Optimization

Combinatorial optimization is the process of searching for maxima (or minima) of an objective function F whose domain is a discrete but large configuration space (as opposed to an N-dimensional continuous space). Some simple examples of typical combinatorial optimization problems are: The space of possible solutions is typically too large to search exhaustively using pure brute force. In some cases, problems can be solved exactly using Branch and Bound techniques. However, in other cases no exact algorithms are feasible, and randomized search algorithms must be employed, such as: A large part of the field of Operations Research involves algorithms for solving combinatorial optimization problems.

More Information

Several excellent surveys of global optimization techniques are available on the Web; most of these techniques are useful for solving combinatorial optimization problems. Back to Glossary Index