Enumeration methods 1: Unterschied zwischen den Versionen

Aktuelle Version vom 1. Juli 2013, 22:36 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.

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 costs a salesman has, when he wants to travel between a location i and a location j.

Table 1:

Solution

Solution: Explicit complete enumeration

First you change every undesirable cost coefficient ${\displaystyle c_{ij}}$ from "i to j" with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \infty

(=infinite), e.g. the elements of the main diagonal and elements with unusual high transportation costs (e.g. ${\displaystyle c_{32}}$). 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 now 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 costs of 86.

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
(compare table 4)

Table 4:

If you transform table 4 with the Hungarian method ( Assignment problem: Hungarian method ) you get the following table 5.

Table 5:

The table 5 contains additional 0 - elements, which has to be considered in the assignment process. In the next step you have to determine the minimal detours of each 0 - element. This is performed by adding the second lowest element in each row and column to every 0 - element. (compare table 6)

Table 6:

As you can see the highest minimal detour is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3 \to 1

with 4. Now you cross out row number 3 and column number 1. You also set  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{13}^{*} = \infty 
 to prevent from  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3 \to 1 \to 3
 (compare table 7).

Table 7:

Now you proceed just like you did with table 6 and determine the minimal detours. As you can see the highest minimal detour is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1 \to 2

with 2. You cross out row number 1 and column number 2 and proceed the same with the generated matrix. With this algorithm you finally get the optimal tour  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3 \to 1 \to 2 \to 4 \to 5 \to 3 \to 1
 with costs of 86. (compare graphic 1).

Graphic 1:

Solution: Incomplete enumeration

There are plenty methods for incomplete enumeration like the bounded enumeration. The starting table of the algorithm is again table 1. The algorithm has the following steps:

• Step 1: produce the cost-reduced table 2

• Step 2: note all elements that lead from the a starting point to an arbitrary point

• Step 3: choose the minimum from step 2 and add the minimal route element

• Step 4: repeat step 3 until you have a complete route

• Step 5: add leafs to the branches of the enumeration tree until the total costs are equal or bigger than the costs of the starting solution

For our example you get the optimal solution of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1 \to 3 \to 5 \to 4 \to 2 \to 1

 with costs of 87 (compare grahic 2)

Graphic 2:

The framed orders and suborders of the enumeration tree determine just a starting solution. The other orders are necessary for the optimal solution. In this case the optimal solution is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3 \to 1 \to 2 \to 4 \to 5 \to 3 \to 1

 with costs of 86. 

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