Combinatorial Optimization Problems

Why

Often the feasible set of an optimization problem is set with many, say $2^{100}$, objects. Often the size grows exponential in the size of the representation.

Definition

An optimization problem $(\mathcal{X} , f)$ is called a combinatorial (a combinatorial optimization problem) if $\mathcal{X} $ is a finite set. Usually, the language is meant to connote that the set is large, with respect to some predetermined notion of size.