Enumeration methods 5: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Zeile 3: | Zeile 3: | ||
= Enumeration methods = | = Enumeration methods = | ||
− | == | + | == Theory == |
=== Introduction === | === Introduction === | ||
Zeile 9: | Zeile 9: | ||
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. | 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. | 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 | + | 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. | 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. | ||
Zeile 24: | Zeile 24: | ||
==== Incomplete enumeration ==== | ==== 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. | 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 == |
Version vom 26. Juni 2013, 13:31 Uhr
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.