Discrete Optimization Task

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

• AKA: Combinatorial Optimization.
• Context:
  • It can range from being an Exact Combinatorial Optimization Task to being an Approximate Combinatorial Optimization Task.
  • It can be solved by a Combinatorial Optimization System (that implements a combinatorial optimization algorithm.
  • It can have optimization solutions as weighted multisets.
• Example(s):
  • Vehicle Routing Task.
  • Traveling Salesman Task.
  • Minimum Spanning Tree Task.
  • Knapsack Problem.
  • Develop the best airline network of spokes and destinations
  • Decide which taxis in a fleet to route to pick up fares
  • Determine the optimal way to deliver packages
  • Determine the right attributes of concept elements prior to concept testing.
• Counter-Example(s):
  • a Metric Space Optimization Task.
• See: Similarity Search Task, Combinatorics, Constrained Discrete Optimization.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/combinatorial_optimization Retrieved:2015-6-13.
  • In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible. It operates on the domain of those optimization problems, in which the set of feasible solutions is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the traveling salesman problem ("TSP") and the minimum spanning tree problem ("MST"). Combinatorial optimization is a subset of mathematical optimization that is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, machine learning, mathematics, auction theory, and software engineering. Some research literature considers discrete optimization to consist of integer programming together with combinatorial optimization (which in turn is composed of optimization problems dealing with graph structures) although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find solutions to mathematical problems.
• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/combinatorial_optimization#Applications Retrieved:2015-6-13.
  • Applications for combinatorial optimization include, but are not limited to:
    • Developing the best airline network of spokes and destinations
    • Deciding which taxis in a fleet to route to pick up fares
    • Determining the optimal way to deliver packages
    • Determining the right attributes of concept elements prior to concept testing

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'.

---