Enumeration methods 5
Inhaltsverzeichnis
Enumeration methods
Theory
Introduction
Enumeration methods are used to solve combinatorial optimization problems. Combinatorial optimization problems are problems where decision variables are binary, expressing that an object (e.g. graph, edge, node) is chosen or is not chosen. This leads to a lot of possible solutions with the difficulty of selecting and finding solutions that are more optimal than others. Real world examples of such problems include the scheduling of machines in production planning, aircraft rotation/crew scheduli in airline businesses and transport routing/scheduling in logistics. When modelled in a formal way, these problems are subproblems of either allocation problems, permutation problems (where the "Travelling salesman problem" belongs to -> example), selection problems (like "Knapsack problem") or clustering problems.
The number of existing possible alternative solutions of a combinatorial optimization problem can be very large. It is determined by the computational complexity. For example, for an allocation or sequence problem, there are n(n-1)(n-2)...1 = n! alternative solutions, meaning it has a computational complexity of "n factorial". So even with today's computing power, computing all possible solutions to a not-too-big TSP can be impossible. Therefore the goal of most enumeration methods is to cut down the complexity with certain algorithms.
Types of enumeration methods
Explicit complete enumeration
Full enumeration of all possible alternatives and comparision of all of them to pick the best solution. Can be very expensive or even impossible for more complicated problems (->see above).
Implicit complete enumeration
Parts of the solution space that are definitely sub-optimal are excluded. This reduces complexity because only the most promising solutions have to be considered. For implicit complete enumeration, methods like Branch & Bound, limited enumeration and dynamic optimization can be used.
Incomplete enumeration
Selecting alternatives by only looking at parts of the solution space by applying certain heuristics. This provides approximate solutions, but not necessarily optimal ones.
Example
Presentation of the problem
The example shown above is a so-called Travelling Salesman Problem (TSP). TSPs can be characterized by a graph with a number of cities (nodes) and connections (edges) between these cities. Here The goal is to find the shortest route from a start city through all other cities to the end city, with the condition that each city is only visited once.
Mathematical model:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): min D = \sum \sum \sum d_{ij} x_{ij}
where Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{ij} = \{
