Discrete Optimization Task

From GM-RKB
(Redirected from discrete optimization task)
Jump to navigation Jump to search

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