Enumeration methods 2
Inhaltsverzeichnis
Theory
Enumeration methods can be split up in complete enumeration methods and incomplete enumeration methods along the following diagram:
Explicit complete enumeration
Explicit complete enumeration methods are methods of operations research which are used to solve an optimization problem, where no analytical solution algorithms exist and the solution space is finite. It determines all feasible solutions. The optimal solution will be found by comparison. Due to the high computational complexity (in n variables with k possible values, kn solutions arise), this method is applicable only for very small problems. In general, you will move to limited enumeration, branch-and-bound or dynamic optimization.
Implicit complete enumeration
Dynamic methods
see http://michaelcarteronline.com/FOME/pdf/chap7.pdf [Dynamic optimization]
Branch & Bound
see Branch & Bound
Limited Enumeration
Limited enumeration Is a method of operations research. The procedure corresponds to complete enumeration, but the algorithm is aborted when a time or node limit is reached, or better - than the already known - solutions are not expected. The method is based directly on the enumeration of sequentially organized full enumeration. Before the enumeration process starts, general heuristic methods are used. With them an initial solution is calculated. An upper bound of the initial costs Is generated (enumeration limit). If, during the enumeration process a solution is reached or exceeded, the calculation of this solution is stopped and you start to build another solution. It skips groups of branches of full enumeration. When - during the enumeration process - a solution is found and the costs are below the existing bound, you continue with these new costs as the limit of the calculation. When the enumeration is done, the optimal solution is the last bound which was created. For the operation of the limited enumeration, it is very important to reduce that problem. It corresponds to the determination of costs lower limits on branching and bounding. By “reducing” of the problem, a separation of basic costs and solution-dependent costs is introduced. It should help to increase the cost during the enumerative structure of solution. Thus non-optimal solutions are seen early and large groups of branches of the full enumeration can be skiped.
Incomplete enumeration
see heuristics
Example
for complete enumeration applied on a travelling salesman problem:
If you have n different locations, you get (n-1)! solutions. For n=6 you have 5! = 120 solutions. The number of the different steps you get with the formula e(n-1)!, i.e. for n=6 you got 325 steps.
The optimal solution is A-B-F-D-C-E-A or A-E-C-D-F-B-A with a length of 59 km. (We dispensed with a listing of all steps).
Presentation of the problem
As we have seen the implicit complete enumeration is very complex, so we start at the basis of an assignment problem. The difference is, that you have distances instead of costs. You have to minimize the distances between the locations of i and j:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): min D = \sum_{i=1}^n\sum_{j=1}^n d_{ij}x_{ij}
with the following constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=1}^n x_{ij} = 1
for j = 1,2,…,n
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j=1}^n x_{ij} = 1
for i = 1,2,…,n
If we solve for example chart 1 with the simplex method you get the following reduced chart with distances:
Solution
Now we want to solve this TSP with limited enumeration. To limit the possible solutions we start the enumeration at the minimum distance of 53 km (see chart above). Everytime we get a longer distance as the best known distance yet (61 km (heuristic method)) we stop the enumeration. 61 is called the enumeration limit. We get the following chart with just 14 steps:
L is the length of the path and L* is the minimum distance of 53 km including the reduced distances of the sequences (see chart 3). The optimal solution is found in step 10 with a distance of 59 km.
In the following figure you can see additionally the decision tree of this example of the limited enumeration.
In the end it is to say, that also this method of limited enumeration is only applicable on small examples with a clear amount of locations.
Sources
http://www.wirtschftslexikon.de
Müller-Merbach, H. (1970): Optimale Reihenfolgen, 1. version, Heidelberg/Berlin
Müller-Merbach, H. (1992): Operations Research, 3. version, München
