Abstract
M.Sc. (Computer Science)
The Travelling Salesman Problem (TSP) comprises the following: A salesman is required, by definition of his job description, to visit a set of cities. He leaves from a base city, visits each of the other cities exactly once and then returns to his base city. In travelling between city pairs, he incurs certain costs. It is a travelling salesman's constant endeavour, therefore, to find the cheapest route. A combinatorial optimisation problem involves the selection of the best alternative from a finite set of alternatives. The TSP is one of the best known and most studied combinatorial optimisation problems. At present, the branch-and-cut algorithm of Padberg and Rinaldi is the most successful algorithm for solving large-scale instances of the TSP. Padberg and Rinaldi used a general LP solver to solve the subproblem P(L, F0 , F1 ), where L is a set of side constraints, F0 is the set of variables fixed at 0 and F1 is the set of variables fixed at 1. As noted by Smith and
Leenen, however, this subproblem has a special structure that was exploited by them to solve the subproblem more efficiently. In this dissertation, we would like to present improvements on Leenen's contribution. For this purpose, we compared our results with those of a commercial LP solver. It was found that our program on average executed in half the time of that of the commercial LP solver. The problem P(L, F0 , F1;) has to be solved many times in the branch-and-cut algorithm before a solution to the TSP is obtained. For large-scale instances of the TSP, a substantial portion of the execution time of the entire branch-and-cut algorithm is spent in the linearprogram optimiser. The branch-and-cut algorithm could,• therefore, be potentially more efficient if the special structure were utilised. We constructed a full implementation of the branch-and-cut algorithm, utilising the special structure. We did not, however, implement all the refinements discussed by Padberg and Rinaldi. Padberg and Rinaldi used four classes of TSP constraints: subtour elimination, 2-matching, comb and clique-tree inequalities. Owing to time constraints and the complexity of identifying the other classes of constraints, we decided to implement subtour elimination constraints only. We subsequently compared our results with those of Padberg and Rinaldi, and realised that we totally underestimated the importance of using more classes of constraints. Our search trees had become extremely huge. We realised, therefore, that more classes of constraints were essential for solving large instances of the TSP. Even though numerical errors still posed a problem, they might disappear if the size of the search tree were reduced to that obtained by Padberg and Rinaldi.