A short description of our iterative Lin-Kernighan heuristic and its experiments H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga Contact to: ndhung@taurus.cs.miyazaki-u.ac.jp Here is a short description of our implementations. There are two main modifications in our implementations. First, we used some extra data structures together with the two-level tree to implement the temporary flip operation in a constant time (with the condition that the depth of the search is bounded) and the permanent flip operation in O(N**0.5) time. Of course the time complexities of other operations (next, prev, between) are constant. I think that the idea of the segment tree may be modified to work with the two-level tree to gain the same time complexity with our implementation but have not tested this yet. The original segment tree has designed to work with the array data structure, thus the time complexity of permanent flip operation is O(N). The second modification is that we check for a sequence of moves which consists of a valid 5-opt move followed by any valid 3-opt move as a basic move. This follows Helsgaun's idea. However, Helsgaun used 5-opt move as a basic move, making the running time of his implementation enormous (although the tour quality is very good). By choosing a valid 3-opt move as a basic move, we try to balance between the tour quality and the running time. As a result, our implementation can handle the one-million-city instance (and even bigger if the memory of our computer allows) in a reasonable CPU time. Other modifications are minor. We use backtracking for searching the first 5-opt move. The breadths of the search are (3,3,2,2), i.e. 3 first best choices for x2, 3 first best choices for x4, 2 first best choices for x6, and 2 first best choices x8. With a given x0, both candidates for x1 are checked. The depth of the search is limited to 100. For speeding up the algorithm, we used the don't look bit concept, a cache mechanism like the one described by Bentley, and an extra cache that stores the lengths of all edges of the current tour.