Enumeration methods 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(Die Seite wurde neu angelegt: „There are two solution sets for difficult combinatorical optimization problems available: complete and incomplete enumeration methods. These solution sets also…“) |
Pvogt (Diskussion | Beiträge) |
||
| Zeile 9: | Zeile 9: | ||
==== Explicit complete enumeration ==== | ==== Explicit complete enumeration ==== | ||
| − | + | One possibility to solve a problem is explicit complete enumeration. The algorithm generates consecutively a enumeration tree with all possible solutions and memorizes the current best solution of the examined problem. | |
==== Implicit complete enumeration ==== | ==== Implicit complete enumeration ==== | ||
| + | |||
| + | Another possibility to exactly solve a combinatorical optimization problem is implicit complete enumeration. The algorithm consecutively cuts of all subsets of the solution space in which, under predetermined conditions, no optimal solution could be expected. The algorithm generates consecutively a enumeration tree of the remaining solution space. | ||
=== Incomplete enumeration === | === Incomplete enumeration === | ||
| + | |||
| + | |||
== Example == | == Example == | ||
Version vom 1. Juli 2013, 15:13 Uhr
There are two solution sets for difficult combinatorical optimization problems available: complete and incomplete enumeration methods. These solution sets also apply on integer or mixed-integer optimization problems.
Inhaltsverzeichnis
Theory
Complete enumeration
A complete enumeration method guarantees, that from all possible solutions the optimum is chosen. Algorithms that always provide the optimal solution are called exact methods.
Explicit complete enumeration
One possibility to solve a problem is explicit complete enumeration. The algorithm generates consecutively a enumeration tree with all possible solutions and memorizes the current best solution of the examined problem.
Implicit complete enumeration
Another possibility to exactly solve a combinatorical optimization problem is implicit complete enumeration. The algorithm consecutively cuts of all subsets of the solution space in which, under predetermined conditions, no optimal solution could be expected. The algorithm generates consecutively a enumeration tree of the remaining solution space.
Incomplete enumeration
Example
Presentation of the problem
Solution process
Sources
Neumann, K.; Morlock, M.: Operations Research, 2.Auflage, Carl Hanser Verlag München Wien, 2002
