README

This is an implementation of the algorithm solving the traveling salesman problem in C++ described in the book "Operational research. selected methods and algorithms, part I" written by Prof. Ph.D. B. Filipowicz (link). It was a group project in the professor's class.

Step-by-step description of what the algorithm looks like. This algorithms was described in the book "Operational research. selected methods and algorithms, part I" written by Prof. Ph.D. B. Filipowicz (link)

step 1.

• step 1 of the vegetarian method.
• if there is not 1 zero in the rows, find the minimum in each column and subtract the minimum from the entire row.
• step 2 of the Hungarian method.
• the same as step 1 of the Hungarian method, only we do it for columns, we find the minimum for each column.
• we set the lower limit
• we add all the minimums in rows and columns. Thanks to this, we set the first limitation.

step 2.

• For each zero ij in turn. we look at the row and column in which zero is located. We find the minimum in this row "i" and column "j" and add these 2 minimum values together.

Example:

ij	A	B	C
A	inf	0	3
B	0	inf	4
C	4	0	inf

In this example we have 3 zeros in position [1,2],[2,1],[3,2].

• We do this for every zero, but we don't take into account the zero itself at the intersection.
• now that we have these values, we sum them for each zero:

[1,2] = 3 + 0 = 3 [2,1] = 4 + 4 = 8 [3,2] = 4 + 0 = 4 [i,j] = min(row) + min(column) = value for the zero balance.

• we determine the maximum of the calculated sums, the so-called penalty.

max{3,8,4} = 8.

• we calculate the second limit by adding our max to the lower limit calculated in step 1. We now have a limit and a limit with *.

• we create a graph/tree, the first element 0 has a limitation, it has no marking.

• we add two more elements to the graph, one with the * constraint and the other with the normal constraint.

• in this table without an asterisk, we remove the column and row with the highest sum in step 2:

Left matrix in a graph

CB*	A	B	C
A	inf	0	3
B	0	inf	4
C	4	0	inf

Right matrix in a graph

CB	A	-	C
A	inf	-	3
B	0	-	4
-	-	-	-

The graph at this stage looks like this:

graph LR
A((Alpha ))
A --> B((CB*))
A --> C((CB))

Loading

step 3.

We assign a value to a vertex in the graph.

LowerEstimate* = LowerEstimate + penalty

graph LR
A((Alpha ))
A --> B((CB* = limit + punishment))
A --> C((CB = limit))

Loading

step 4.

• After deleting the row and column, we make sure that there are infinities on the diagonal:

Right matrix in a graph

CB	A	C
A	inf	3
B	0	inf

step 5

• We check whether the new reduced matrix meets the conditions and has zeros in each column and row, if we do not implement steps 1 and 2 of the Hungarian method.
• We determine the variable h, which is the sum of the subtracted minimum values from steps 1 and 2 of the Hungarian method.

limit = limit + h

step 6

• We assign the value of the newly calculated constraint to the graph:

graph LR
A((Alpha ))
A --> B((CB* = limit + punishment))
A --> C((CB = limit + h))

Loading

step 7

• When the array is 2x2 in size and we have 1 of 2 cases:

ij	A	C
A	in	0
B	0	inf

or

ij	A	C
A	0	inf
B	inf	0

The algorithm is stopped by going to step 8.

• We add the last 2 elements to the graph. The next 2 last elements are AC and BA.

graph LR
A((Alpha ))
A --> B((CB*))
A --> C((CB))
C --> D((AC))
D --> E((BA))

Loading

step 8

• We check whether the last element of the graph has a smaller constraint than the elements ij and ij* coming from Alpha. In the example, these are the elements CB and CB*
• if the element CB is smaller than BA, we go to step 2 and finish the algorithm.
• if the CB* element is smaller, we go to step 9

step 9

• Instead of CB we put inf

  CB*	A	B	C
  A	inf	0	3
  B	0	inf	4
  C	4	inf	inf

• For such an array, we implement steps 1 and 2 of the Hungarian method.

• Go to step 2