Tabu search example question

Question

Could you please help me understand this Tabu search page 7 example:

TS is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as "taboo" ("tabu" being a different spelling of the same word) so that the algorithm does not visit that possibility repeatedly. Tabu search is attributed to Fred W. Glover

I do not understand why an upper triangle is used, and why is this :

The tabu structure now shows that swapping the positions of modules 4 and 5 is forbidden for 3 iterations. The most improving move at this step is to swap 3 and 1 for a gain of 2.

Could you please explain why the triangle and why is it the above statement?

???

Answer 1

The statement

In the exemple of the powerpoint they chose a duration of 3. Each time one swap is made it will be tabu for the next 3 moves.

That's why at step 1 (note: I start at step 0) you have the following statement:

The tabu structure now shows that swapping the positions of modules 4 and 5 is forbidden for 3 iterations. The most improving move at this step is to swap 3 and 1 for a gain of 2.

Swapping 3 and 1 at this step is the best move to increase value.

After your last step (step 3) they actually swap 4 and 5 even if it is tabu because of the aspiration criterion. (20 > 18 which is best value so far).

The triangle

The representation is a triangle because the swapping manipulation is symetric. So you don't need more than an upper triangle to represent your tabu structure.

In each cell of the tabu structure you have the remaining tenure (the duration left for the move to be tabu) of the pair (x,y) = (y,x).

I don't know much about tabu search, but I hope it helps.