Version vom 1. Juli 2013, 18:33 Uhr

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 chapter Dynamic methods

Branch & Bound

see chapter Branch & Bound

Limited Enumeration

Limited enumeration methods are methods 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. Here the enumeration process in general heuristic methods are used, with which an initial solution is calculated. It serves as the upper bound of the initial costs (enumeration limit). If, during the enumeration process a solution is reached or exceeded, the calculation of this solution is stopped and started to build another solution. It skips groups of branches of full enumeration. when, during the enumeration process, a solution is found, the costs are below the existing bound, it continues with these new costs as a 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 can skip the full enumeration.

Incomplete enumeration

see heuristic methods

Example

for complete enumeration applied on a travelling salesman problem:

Chart 1: chart with distances (km) between locations A to F

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:

min D= ∑_(i=1)^n▒∑_(j=1)^n▒〖d_ij x_ij 〗

with the following constraints: ∑_(i=1)^n▒〖x_ij=1〗 for j =1,2,…,n ∑_(j=1)^n▒〖x_ij=1〗 for i = 1,2,…,n

xij =

If we solve for example chart 1 with the simplex method you get the following reduced chart with distances

(hier tabelle einfügen)

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