When Is a Complete Enumeration of Solutions Used

Inhaltsverzeichnis

• 1 Theory
  • 1.1 Explicit complete enumeration
  • 1.2 Implicit complete enumeration
    • 1.2.1 Dynamic methods
    • 1.2.2 Branch & Bound
    • 1.2.3 Limited Enumeration
  • 1.3 Incomplete enumeration
• 2 Example
• 3 Presentation of the problem
• 4 Solution
• 5 Sources

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:

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.

chart 2: a section of the steps of a full enumeration applied on the TSP

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:

chart 3: 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:

chart 4: chart with distances (km) after limited enumeration

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.

image 2: chart with distances (km) between locations A to F

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

When Is a Complete Enumeration of Solutions Used

Source: https://www.wiwi.uni-kl.de/bisor-orwiki/Enumeration_methods_2#:~:text=Explicit%20complete%20enumeration%20methods%20are,will%20be%20found%20by%20comparison.

Share this post