(Redirected from combinatorial optimization)

A Discrete Optimization Task is an optimization task whose input is a discrete search space.

## References

### 2015

1. Schrijver, p. 1

### 2012

• http://en.wikipedia.org/wiki/Optimization_problem#Combinatorial_optimization_problem
• Formally, a combinatorial optimization problem $A$ is a quadruple $(I, f, m, g)$, where
• $I$ is a set of instances;
• given an instance $x \in I$, $f(x)$ is the set of feasible solutions;
• given an instance $x$ and a feasible solution $y$ of $x$, $m(x, y)$ denotes the measure of $y$, which is usually a positive real.
• $g$ is the goal function, and is either $\min$ or $\max$.
• The goal is then to find for some instance $x$ an optimal solution, that is, a feasible solution $y$ with :$m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .$
• For each combinatorial optimization problem, there is a corresponding decision problem that asks whether there is a feasible solution for some particular measure $m_0$. For example, if there is a graph $G$ which contains vertices $u$ and $v$, an optimization problem might be "find a path from $u$ to $v$ that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from $u$ to $v$ that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.