Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory.

Sometimes it is called "discrete optimization", however the latter term is considered to be somewhat different.

Contents

1 Informal definition 2 Formal definition 3 Examples 4 Methods 5 References 6 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,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.)

Examples

Examples of problems are the

• traveling salesman problem,
• the minimum spanning tree problem, and
• linear programming problems.

Methods

Heuristic search methods (meta heuristics), such as

• local search,
• simulated annealing,
• tabu search, or
• genetic algorithms

can be used to find optimal solutions of combinatorial optimization problems. A question of great interest concerns the efficiency of such methods, i.e. the question of whether one search method is better than the other across all types of problems. An answer to this question was provided in the 90's by the no-free-lunch theorem.

References

• William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.
• Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.

Journals

• Journal of Combinatorial Optimization