Discrete Optimization Task

(Redirected from combinatorial optimization)
Jump to: navigation, search

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



  1. Schrijver, p. 1


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