Enumeration methods 1
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
In case of large scale optimization problems the computing time for complete enumeration techniques often exceeds the economic reasonable time. Therefore a use of incomplete enumeration (heuristics) is advised. Incomplete enumeration techniques just search in a subset of the valid solution space. Hence the best generated solution is not necessarily a optimal solution. It is also possible, that a heuristic stops without a valid solution even if there is one.
Example: Traveling Salesman Problem (TSP)
In the following we discuss one examples which we solve with the three enumeration methods mentioned before. The following table shows the cost a salesman has to travel from a location i to a location j.
Table 1:
Solution
Solution: Explicit complete enumeration
First you change every undesirable cost coefficient from "i to j" with ∞ (=infinite), e.g. the elements of the main diagonal and elements with unusual high transportation costs (e.g. ). To reduce the complexity of the explicit complete enumeration process you subtract in every row the lowest cost from all the other costs (compare table 2): Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}^{*} = c_{ij} - min\ c_{ij}
Table 2:
With this table you know look for every possible enumeration.
Table 3:
From table 3 you see that the optimal solution has the order 1 - 2 - 4 - 5 - 3 - 1 with minimal cost of 4.
Solution: Implicit complete enumeration
First you mark every 0 in table 2, where no additional 0 is detected in either the same row or the same column. Then you get four assignments: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1 \to 3,
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3 \to 1,
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4 \to 2,
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5 \to 4
Solution: Incomplete enumeration
Sources
Neumann, K.; Morlock, M.: Operations Research, 2.Auflage, Carl Hanser Verlag München Wien, 2002
Zimmermann, W.:Operations Research, Quantitative Methoden zur Entscheidungsvorbereitung, 6.Auflage, R.Oldenbourg Verlag München Wien, 1992
