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 Traveling Salesman Problem: given the (x, y) positions of N
different cities, find the shortest possible path that visits each
city exactly once.
- Bin-Packing: given a set of N objects each with a specified size
si, fit them into as few bins (each of size B) as possible.
- Integer Linear Programming: maximize a specified linear combination
of a set of integers X1 ... XN subject to a set
of linear constraints each of the form
- Job-shop Scheduling: given a set of jobs that must be
performed, and a limited set of tools with which these jobs can be
performed, find a schedule for what jobs should be done when
and with what tools that minimizes the total amount of time until
all jobs have been completed.
- Boolean Satisfiability: assign values to
a set of boolean variables in order to satisfy a given boolean expression.
(A suitable objective function might be the number of satisfied clauses
if the expression is a CNF formula.)
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