# 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
a1X1 + ... + aNXN <= c.
• 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.