(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 $\displaystyle{ A }$ is a quadruple $\displaystyle{ (I, f, m, g) }$, where
• $\displaystyle{ I }$ is a set of instances;
• given an instance $\displaystyle{ x \in I }$, $\displaystyle{ f(x) }$ is the set of feasible solutions;
• given an instance $\displaystyle{ x }$ and a feasible solution $\displaystyle{ y }$ of $\displaystyle{ x }$, $\displaystyle{ m(x, y) }$ denotes the measure of $\displaystyle{ y }$, which is usually a positive real.
• $\displaystyle{ g }$ is the goal function, and is either $\displaystyle{ \min }$ or $\displaystyle{ \max }$.
• The goal is then to find for some instance $\displaystyle{ x }$ an optimal solution, that is, a feasible solution $\displaystyle{ y }$ with :$\displaystyle{ 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 $\displaystyle{ m_0 }$. For example, if there is a graph $\displaystyle{ G }$ which contains vertices $\displaystyle{ u }$ and $\displaystyle{ v }$, an optimization problem might be "find a path from $\displaystyle{ u }$ to $\displaystyle{ 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 $\displaystyle{ u }$ to $\displaystyle{ v }$ that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.